Theory of Computation 2018 Question Paper — Government College of Eng…

Instructions

• Attempt 5 questions in all selecting atleast two from each section.

Questions

Section - A

• Q1. a) Construct Minimum State automata equivalent to FA. | State | 0 | 1 | |---|---|---| | $\rightarrow q_0$ | $q_1$ | $q_0$ | | $q_1$ | $q_0$ | $q_2$ | | $q_2$ | $q_3$ | $q_1$ | | $q_3$ | $q_3$ | $q_0$ | | $q_4$ | $q_3$ | $q_5$ | | $q_5$ | $q_6$ | $q_4$ | | $q_6$ | $q_5$ | $q_6$ | | $q_7$ | $q_6$ | $q_3$ | b) State and Prove Pumping Lemma for Regular Sets? [20 marks]
• Q2. a) Prove that there exists no finite state machine that accepts palindrome? b) Show that $L = \{0^i 1^i \mid i \ge 1\}$ is not regular? [20 marks]
• Q3. a) Construct NFA for the Regular exp $((a+b)^*aa)^*$ b) State and prove the equivalence of Moore machine and Mealey machine? [20 marks]
• Q4. a) Consider the two regular expressions $R1 = a^*+b^* \quad R2 = ab^*+ab^*+b^*a+(a^*b)^*$. i) Find a string corresponding to R1 but not R2. ii) Find a string corresponding to R2 but not R1. iii) Find a string corresponding to both R1 and R2. b) Construct a DFA equivalent to NFA. | State | 0 | 1 | 2 | |---|---|---|---| | $\rightarrow q_0$ | $\{q_1,q_4\}$ | $q_4$ | $\{2,q_3\}$ | | $q_1$ | $-$ | $q_4$ | $-$ | | $q_2$ | $-$ | $-$ | $\{q_2,q_3\}$ | | $q_3$ | $-$ | $q_4$ | $-$ | | $q_4$ | $-$ | $-$ | $-$ | [20 marks]

Section - B

• Q5. a) What is ambiguity in grammar and how can we remove it? Consider the following grammar $E \rightarrow E+E, E \rightarrow E^*E, E \rightarrow E^\wedge E, E \rightarrow id$ Write an Unambiguous CFG equivalent to the above grammar. b) State the two lemma's used for converting CFG to GNF? [20 marks]
• Q6. a) What are universal Turing machine? Give an example to explain its working? b) Design a Turing machine to multiply two unary numbers? [20 marks]
• Q7. a) Convert the given CFG into CNF $S \rightarrow bA \mid aB, A \rightarrow bAA \mid aS \mid a, B \rightarrow XBB \mid YS \mid b$? b) Construct CFG to generate the following : i) The set of all strings over \{a,b\} containing twice as many a's as b's ii) \{a^n b^m \mid m \neq n, m, n \ge 1\}. [20 marks]
• Q8. a) Differentiate between recursive language and recursively enumerable languages? b) Discuss solvable, semi solvable and unsolvable problems? [20 marks]

Related pages

• Theory of Computation syllabus
• All Theory of Computation papers from 2018

Other years

• Theory of Computation 2018 question paper — end-term
• Theory of Computation 2018 question paper — end-term