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^n|n>=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
