Theory of Computation
HNBGU MCA Previous Question Paper 2022


Differentiate between DFA and NFA with examples.

Give the recursive definition of regular expression. Find
the language described by the regular expression :
ab*
+ a for a,b ℇ ⅀ (An alphabet)


Define Moore and Mealy machines with examples.

Convert the following Mealy machine into an equivalent Moore
machine:


Write the regular expression, for the language which
contains all the strings over an alphabet ⅀ {0,1} ending
with 011.

Minimize the following DFA:


Define context free grammar with example.

Reduce the following grammar into Chomsky Normal Form:
G
= ({S,A,B,C},{A,B},S,{S>aC, A>aB  bAB, B>b,
C>c})


Define Pushdown automaton with example. Is it possible to
construct PDA for context free grammar?

Design a PDA for the language.
L={ww^r  w ℇ
{0,1} and w^r is reverse of w.}


How to define transition in Turing Machine? Give Id
representation of Turing machine with example.

Design Turing machine that accepts the language
L
= {a^nb^nn>=1}

Write short note on any two of the following:
 Pumping lemma for regular sets.
 Chomsky's hierarchy of grammars.
 ℇNFA

State elimination method for converting Finite Automaton to
Regular Expression