Important RGPV Question
CS-501 Theory of Computation
V Sem, CS
UNIT 1-Introduction of Automata Theory
Q.1) Convert the following Moore machine to Mealy.
(RGPV May 2023)
UNIT 2-Types of Finite Automata
Q.1) For Σ = {a, b}, construct DFA’s that accept the sets consisting of
i) All the strings with exactly one ‘a’.
ii) All the string with atleast one ‘a’.
iii) All strings with atleast one ‘a’ and followed by exactly two b’s
(RGPV May 2023)
Q.2) Explain Arden’s theorem and Pumping Lemma.
(RGPV May 2023)
Q.3) Design a Push down automata.
(RGPV May 2023)
Q.4) Draw a DFA to accept string of 0’s and 1’s not ending with the string 01.
(RGPV Nov 2023)
Q.5) Design a DFA to accept string of O’s and 1’s when interpreted as binary numbers would be multiple of 3.
(RGPV Nov 2023)
Q.6) Derive regular expression from this finite automata
(RGPV Nov 2023)
Q.7) Construct an equivalent FA for the given regular expression (0+1)*(00+11) (0+1)*
(RGPV Nov 2023)
Q.8) Compute the Regular Expression for the DFA as shown below.
(RGPV Nov 2022)
Q.9) Design DFA’s for detecting 1001 Sequence without Overlap over the alphabet 2 = {0,1}
(RGPV Nov 2022)
Q.10) Design a NFA that accepts the language over the alphabet, Σ= {0, 1,2} where the decimal equivalent of the language is divisible by 3.
(RGPV Nov 2022)
Q.11) Convert the following NFA to an equivalent DFA.
(RGPV Nov 2022)
Q.12) Construct Non-Deterministic Pushdown Automata (NPDA) to accept the language L= {0n+112n | n> = m} over the alphabet, Σ={0, 1}
(RGPV Nov 2022)
UNIT 3- Grammars
Q.1) What is Ambiguity? Explain taking any two examples.
(RGPV May 2023)
Q.2) Define a context free grammar with example.
(RGPV May 2023)
Q.3) Find the context free grammar with no useless symbols equivalent to
S→AB/Ca, B→BC/AB, A→a, C→aB/b.
(RGPV Nov 2023)
Q.4) What is meant by ambiguous grammar? Test whether the grammar is ambiguous or not.
(RGPV Nov 2023)
Q.5) Construct the following CFG grammar
i) an bn cn where m, n ≥ 1
ii) Obtain a CFG to generate a integer
(RGPV Nov 2023)
Q.6) Let G be the grammar given by S→aABB/aAA, A→aBB/a, B→bBB/A construct the PDA that accepts the language generated by this grammar G.
(RGPV Nov 2023)
Q.7) Define the context free grammars in the 4 tuple from (V, T, P, S) for the given languages on ∑ (a, b).
i) All strings having atleast two ‘a’s.
ii) All possible strings not containing triple ‘b’s.
(RGPV Nov 2023)
Q.8) Identify the language, L generated by the following grammar, G:
G=({S, A, B), {a, b}, {S→Aa, A→a|B, B→bB|b}, S).
(RGPV Nov 2022)
Q.9) Find a regular grammar that generates the language on {a,b} consisting of all strings with exactly one a’s and no more than two b’s.
(RGPV Nov 2022)
Q.10) Construct context free grammars to accept the language L = {an+2, bm+1 | n = m} over the alphabet, ∑ ={a, b}
(RGPV Nov 2022)
Q.11) Show that the following language on ∑ = {a, b, c} is not context-free.
(RGPV Nov 2022)
UNIT 4-Friction
Q.1) Design a CFG.
(RGPV May 2023)
Q.2) Explain DPDA and NPDA with taking a suitable example.
(RGPV May 2023)
Q.3) Construct the PDA accepting the language.
i) L= {(ab)n|n >= 1} by empty stack.
ii) L{wwR|w is in (a+b)*} by empty stack.
iii) L= {a2n bn | n >= 1} by empty stack.
(RGPV Nov 2023)
Q.4) Construct corresponding CFG for the following NPDA.
(RGPV Nov 2022)
Q.5) Give a Deterministic PDA that accepts {am bn cn |m,n ≥0} over the alphabet, ∑ ={a, b, c}.
(RGPV Nov 2022)
Q.6) Give an NPDA that simulates the following grammar (S is start symbol):
S→aBB |cDD
B→CD | aS
D→dD|d
(RGPV Nov 2022)
UNIT 5-Turing Machine
Q.1) Explain Recursively enumerable language and decidability.
(RGPV May 2023)
Q.2) What is the difference between a recursive and recursively enumerable languages?
(RGPV Nov 2023)
Q.3) What do you mean by saying that the halting problem of TM is undecidable?
(RGPV Nov 2023)
Q.4) Construct Turing Machine (TM) to accept the language L= {0n| 1n |2n | n >= 0} over the alphabet, Σ ={0, 1, 2}
(RGPV Nov 2022)
Q.5) Prove that a language L is recursive if and only if L and L are recursively enumerable.
(RGPV Nov 2022)
Q.6) Prove that there is no algorithm that determines whether an arbitrary Tuning Machine halts when run with the input string 101.
(RGPV Nov 2022)
Q.7) Prove that the problem of determining whether for a Turing machine M the language L(M) is regular is undecidable.
(RGPV Nov 2022)
EXTRA QUESTIONS-
Q.1) Describe the following sets by regular expression.
i) Strings containing 1100 as substrings.
ii) The set of all strings of 0’s are 1’s ending with 00. ………}.
iii) {Λ, a, aa, aaa, aaaa, ………………..
(RGPV May 2023)
Q.2) Write short notes on: (Any three)
i) Halting problem
ii) Turing machine
iii) Chomsky Normal form
iv) 2 way DFA
(RGPV May 2023)
Q.3) Write short notes on (Any three)
i) Post correspondence problem
ii) Halting problem
iii) Closure property of regular grammar
iv) Turing machine
(RGPV Nov 2023)
— Best of Luck for Exam —
