Theory of Computation 2018 Question Paper — Government College of Eng…
The 2018 Theory of Computation previous year question paper (Government College of Engineering and Technology, Jammu), with every question and its marks.
- University: Government College of Engineering and Technology, Jammu
- Subject: Theory of Computation
- Course: Theory of Computation
- Branch: COMPUTER/I.T. ENGINEERING
- Year: 2018
- Paper: end-term
- Duration: 180 minutes
- Total marks: 100
Instructions
- Attempt five questions in all selecting at least two questions from each Section.
- Each question carries 20 marks.
Questions
Section - A
- Q1. Design DFA and write down Regular Expression for the following language over \{ a, b \}: (a) All strings having at least three a's and at least two b's. (b) All strings having substring bbb. (c) All strings not having substring aab. (d) All strings having length at most 5. (e) All strings having even number of a's and even number of b's. [20 marks]
- Q2. (a) Prove the Arden's Theorem including the proof for unique solutions given by $R = Q P^*$ (b) Construct a DFA equivalent to $M = (\{q_0, q_1, q_2, q_3\}, \{0, 1\}, \delta, q_0, \{q_3\})$ where $q_3$ is the final state. The $\delta$ function is as follows: | | 0 | 1 | |---|---|---| | $\rightarrow q_0$ | $\{q_0, q_1\}$ | $q_0$ | | $q_1$ | $q_2$ | $q_1$ | | $q_2$ | $q_3$ | $q_3$ | | $q_3$ | $\phi$ | $q_2$ | [20 marks]
- Q3. Construct a Minimum state automata equivalent to the following transition diagram. [20 marks]
Section - B
- Q4. Define Mealy and Moore Machine. Explain the process of converting Mealy to Moore Machine. [20 marks]
- Q5. What do you mean by Chomsky Hierarchy? Write down various restrictions on different types of grammar. Explain with example. [20 marks]
- Q6. What do you mean by Push Down Automata? Design a Pushdown Automata for the language $L = \{0^m 1^n \mid m = n \text{ or } m = 2n \}$ [20 marks]
- Q7. Design a Turing Machine for the language $L = \{a^n b^n c^n \mid n \ge 1\}$. Explain the logic in detail. Give the trace or instantaneous description of $W = \text{aaabbbccc}$. [20 marks]
- Q8. Write short notes on the following: (a) Decidability (b) Context Free Grammar (c) Ambiguous Grammar (d) Non - Ambiguous Grammar. [20 marks]
Related pages
Other years
- Theory of Computation 2018 question paper — end-term
- Theory of Computation 2018 question paper — end-term