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

Instructions

• Attempt five questions in all selecting at least two questions from each section. Each question carries 20 marks.

Questions

Section-A

• Q1. (a) Define the following with the help of example : Alphabet, Language, Finite Automata, Regular Expression, Moore Machine. (10) (b) Define a regular expression. What are its properties ? (10) [20 marks]
• Q2. (a) Design a Non-deterministic Finite Automata for the language over {a, b} that ends with aba. Convert it into Deterministic Finite Automata. (10) (b) Prove that for every NFA that is accepting the language L there exists a DFA which accepts the same language L. (10) [20 marks]
• Q3. Construct a Minimum State Automata equivalent to the FA whose transition table is as shown : | | 0 | 1 | |---|---|---| | $\rightarrow q_0$ | $q_1$ | $q_5$ | | $q_1$ | $q_6$ | $q_2$ | | $(q_2)$ | $q_0$ | $q_2$ | | $q_3$ | $q_2$ | $q_6$ | | $q_4$ | $q_7$ | $q_5$ | | $q_5$ | $q_2$ | $q_6$ | | $q_6$ | $q_6$ | $q_4$ | | $q_7$ | $q_6$ | $q_2$ | [20 marks]
• Q4. (a) Using Arden's theorem, construct a regular expression for the transition diagram given below : (10) (b) Convert the given Mealy machine into Moore machine : (10) | State | Input $a = 0$ | Input $a = 1$ | |---|---|---|--- | | State | Output | State | Output | | $\rightarrow q_1$ | $q_3$ | $0$ | $q_2$ | $0$ | | $q_2$ | $q_1$ | $1$ | $q_4$ | $0$ | | $q_3$ | $q_2$ | $1$ | $q_1$ | $1$ | | $q_4$ | $q_4$ | $1$ | $q_3$ | $0$ | [20 marks]

Section-B

• Q5. Write down the Pumping Lemma for regular sets. How is it used to prove that a language is not regular ? Using Pumping Lemma prove that $L = \{a^w \mid w = 2^n \text{ and } n \ge 0\}$ is not Regular Language. [20 marks]
• Q6. (a) Construct a PDA for the following language : (10) $$L = \{a^n b^{2n} \mid n \ge 1\}$$ (b) Design a PDA for odd palindrome over {a, b}. (10) [20 marks]
• Q7. Write down the formal definition of Turing Machine. Design a Turing Machine for the Language $L = \{waw^r, wbw^r \mid w \in \{a, b\}^*\}$. [20 marks]
• Q8. Write short notes on : (a) Chomsky Hierarchy (10) (b) Ambiguous Grammar. (10) [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