GALGOTIAS COLLEGE OF ENGINEERING AND TECHNOLOGY

GREATER NOIDA

Theory of Automata and Formal Languages

SUBJECT CODE: BCS-402 (2023-24)

QUESTION BANK

BCS-402.1 Analyse and design finite automata, pushdown automata, Turing machines, formal
languages, and grammars
BCS-402.2 Analyse and design, Turing machines, formal languages, and grammars
BCS-402.3 Demonstrate the understanding of key notions, such as algorithm, computability,
decidability, and complexity through problem solving
BCS-402.4 Prove the basic results of the Theory of Computation
BCS-402.5 State and explain the relevance of the Church-Turing thesis

CO1

Q1 Define Alphabet, string, language and automata.

Q2. What do you understand by Epsilon Closure of a state in Finite Automata.
Q.3 Differentiate between L* and L +.
Q4. Differentiate between Deterministic and Non Deterministic Finite Automata.
Q5. Differentiate between Moore and mealy machine and explain the algorithm for
mealy to Moore and Moore to mealy conversion with an example.
Q6. Design finite automata accepting the following language over alphabet {0, 1}
(a) The set of all strings with three consecutive 000’s.
(b) The set of all strings whose last two symbols are same.
(c) The set of strings not containing three consecutive ones.
(d) L= {w :|w| mod 3=0}
(e) L= {(01)2i12j/i≥1,j≥1}
(f) The set of strings in which total numberof0’s is divisible by3.
(g) Even number of 0’s followed by single 1.
(h) L= {am bn| m is divisible by 2 and n is divisible by 4}.
(i) All the strings in which the third symbol from right end is always 1.
Q7. Construct a minimal DFA accepting set of strings over {a, b} in which anbmcl, where
n, m and l is greater than or equal to 0.
Q8. Explain the steps of Minimization of DFA with example.
Q9. Describe the steps conversion of ɛ-NFA to NFA and NFA to DFA with an example.
Q10. Give the various applications of FA.
Q11. Define Mealy and Moore Machine with suitable example.
Q12. Design a Finite Automata to accept the binary number divisible by 3.
Q13. Define Deterministic Finite Automata. Design FA to accept the binary number
divisible by 5.
Q14. Design a FA to accept the strings always ending with 101.
Q15. Design a FA to accept the ternary number divisible by 5.
Q16. Design a DFA that accepts even numbers of a’s and even numbers of b’s.
Q17. Design a DFA that accepts all those strings of a’s and b’s in which number of a’s is
even and number of b’s is divisible by 3.
Q18. Minimize the following DFA having q5 as Final state:

Q19. Define a FA that accepts set of strings containing exactly four 1’s in every string
over ∑ = {0, 1}.

Q20. Construct DFA equivalent to NFA where transition is defined in the table as

Q21. Convert following NFA to DFA and describe the language it accepts:

Q22. Consider the following ɛ-NFA for following:

 i) Compute ɛ-closure of each state.
ii) Convert the automata to DFA.

Q23. For the below transition diagram of a NFA, Convert it to an equivalent DFA.

Q24. Construct an NFA without E- moves corresponding to the below NFA.

Q25. Construct the minimum state automata equivalent to DFA described by the below
figure.

Q26. Define Mealy machine. Convert the following Mealy machine into equivalent Moore
machine:
Q27. Construct DFA accepting each of the following language:-
(a) L = {w є {a, b}* / w has an odd number of a’s or even number of b’s.}
(b) L = {w є {a, b}* / w has neither aa nor bb as substring}
(c) L = {w є {a, b}* / w has both ab and ba as substring}
(d) L = {w : na (w) mod 3> nb (w) mod 3, where na (w) represent no. of a in w and nb (w)
represent no. of b in w}

Q28. Minimize the given Finite automata:

Q29. Minimize the given Automata:

Q30. Explain the applications and limitations of finite automata.

Q31. What is extended transition functionδ*? Explain with example.
Q32. Define and give the difference between positive closure and Kleene closure.

CO2

Q.1 Write down regular expression corresponding to each of the following language over {0,
1}
a) The language of all strings ending with 1 and don’t contain 00.
b) The language of all strings containing both 11 and 010 as substring.
c) The set of all strings over Σ = {0, 1} without length two.
d) The set of all strings of 0’s and 1’s such that every pair of adjacent 0’s appears before
any pair of adjacent 1’s.
e) {an bm , n ≥ 1, m ≥ 1, nm ≥ 3}
f) {a bn w : n ≥3, w ɛ {a, b}+ }
g) {an : n ≥ 0, n≠ 3}
h) The language of all strings in which every 0 is followed immediately by11.
i) The language of all strings that do not contain substring 110.
j) The language of all strings containing at least two 0’s.
k) The language of all strings that begin or end with 00 or 11.

Q.2 Find the regular expression corresponding to the automaton given in following figure using
Arden’s theorem.
a) b)

Q.3 State the concept of Pumping Lemma.

Q4. Proof that the following sets are not regular using pumping lemma concept.
a) {anb2n | n>0};
b) {anb2n| 0<n<m};
c) {ap | p is a prime}
d) {aibjck | k>i+j}

Q5. State and prove Arden’s theorem.

Q6. State and Prove Kleen Theorem.
Q7.Explain the Closure properties of Regular Languages.
Q8. Explain Pigeonhole Principle with context of regular Languages.
Q9. Describe the applications of Pumping Lemna.
Q10. Determine whether complement of non- regular language is also non-regular with an
example.
Q11. State and prove that regular languages are closed under union, concatenation, Kleen
closure.
Q12. Prove that the language L= {0n| n is prime} is not regular.
Q13. Find the regular expression of given FA using Arden’s theorem.

Q14. Give the regular expression for the following:

i) The set of all strings over {0, 1} that does not end with 01.
ii) The set of all strings over {a, b} containing exactly two a’s.

Q15. Using Pumping Lemma for Regular language, prove that language L= {yy/ y }
is not regular.
Q16. Prove that L = {aibi | i ≥ 0} is not regular.

CO3
Q1. Define Context Free Grammar with example.
Q2. Define Backus Naur Form.
Q3. Define ambiguity and inherently ambiguous grammar with example.
Q4. Show that the grammar G with following production is ambiguous.
S → a | aAb | abSb, A → aAAb | Bs

Q5. Define Derivation tree or parse tree. Differentiate between Leftmost and Rightmost
Derivation Tree with an example.
Q6. Find the parse tree for the string aabbbbb considering the productions-S→AB| , A→aB,
B→Sb.
Q7. Give the steps of Simplification of Grammar with an example.
Q8. Explain the procedure of Removal of Null Productions in Grammar.
Q9. Describe the process of removal of Unit Production for a Grammar...
Q10. Remove the Unit productions from the following grammar:

a) S→ aSb| A, A→ cAd| cd
b) S→ A/bb, A→ B/b, B→ S/a
Q11. Convert the following CFG into CNF: S → ASA | aB, A → B | S, B → b | ε.
Q12. Define Chomsky Normal Form with example.
Q 13. Define Greibach Normal Form (GNF) with suitable example.
Q14. Explain the classification of Grammar using Chomsky Hierarchy.
Q15. Differentiate between Right Linear and Left Linear grammars.
Q15. What is Left Recursion. Give the steps for removal of Left Recursion.
Q16. Convert the following CFG into GNF: S → aSbA |A, A → Sa | a.
Q17. Why is left recursion not desirable in Grammar. Remove left recursion from the
following
E → E + T| T , T → T * F | F, F → (E) | id

Q18. The following grammar generates the language consisting of all strings of even length:
S →AS | ε, A → aa| ab | ba | bb.

Give left-most and right-most derivations for the following strings:

i) bbbbbbba (ii) baabab (iii) aaabbb
Q19. Determine the type of the grammar: S → aAb | ε, A → aA | Ab| a| b
Q20. Convert CFG to CNF, Consider the given grammar G1:
S → ASB
A → aAS|a|ε
B → SbS|A|bb

Q21. Consider the following productions:

S→aB |bA
S→aS |bAA|a
S→bS |aBB|b
For the string aaabbabbba, find
a). the left most derivation ,
b). the right most derivation , and
c). the parse tree

Q.22. Write a CFG for language L = {0i1j2k | k <= i or k <= j}

Q.23 Write a CFG for the language L = {wcwr | w ϵ (a, b)*}
Q.24 Define Greibach normal forms for a CFG.Consider the grammar G with following
production rules:
S→AB | AC
A→ aA | bAa | a.
B→ bbA | aB | AB
C→aCa | aD
D→ aD | bC.
Convert the above grammar into Greibach Normal Form.

Q.25. Convert the following grammar into Finite automata:

A -> aB/bA/b
B -> aC/bB
C -> aA/bC/a
Q 26. What is inherent ambiguity? Explain with the help of suitable example.
Q27. Determine the language generated by grammar
S -> Sab | aSb | abS| baS| bSa| Sba|
aS| a

CO4

Q1. Construct a PDA that accepts L = {0n 1n | n ≥ 0}.

Q2. Construct a PDA that accepts L = { wwR | w = (a+b)* }.
Q3. Construct a PDA from the following CFG.
G = ({S, X}, {a, b}, P, S)
Where the productions are −
S → XS | ε , A → aXb | Ab | ab

Q4. Design a non deterministic PDA for accepting the language L = {anbncm | m, n>=1}.
Q5. Distinguish between DPDA & NPDA?
Q6.Design PDA for language: L = {0n1m2m3n | m, n >= 0}.
Q7. Construct a PDA M equivalent to grammar with following productions:
S -> aAA, A-> aS / bS / a
Also, check whether the string ‘abaaaa’ is in M or not.
Q8. Construct the PDA for the language where R stands for
reverse string.
Q9. Describe closure properties of Context Free Language with examples.

Q10. Write short note on

i. Finitness Problem for CFL

ii. Emptiness Problem for CFL

Q11. Explain Pumping Lemna for Context Free Language.

Q12. Construct a Two Stack PDA for accepting the language
L= { anbncndn | n ≥0}.

Q13. Explain Two stack PDA.

Q 14. Construct context free grammar G corresponding to following context free
language, then construct PDA corresponding to G
L = { 0 n 12n | n ≥1}
Q15. What in nondeterministic PDA? Explain with the help of transition function.
Q16. Design a PDA for the following language: L={ai b jc k / i=j or j=k }
Q17. Prove that the following Language L= {anbn c n} is not Context Free.
Q18. Is Context free Language closed under union? If yes give an example.
Q19. What is Push Down Automata (PDA). Explain with an example.
Q20. Construct a PDA equivalent to the following CFG productions:
S→aAA

A→aS/bS/a
Q21. Construct PDA to accept L={0n1 n/ n>=0}
Q22. Construct PDA from the following CFG.
 G= ({S, X}, {a, b}, P, S) where the productions are

S→XS/ ε

X→aXb/Ab/ab

Q23. Consider the CFG ({S,A,B},{a,b},P,S)

where the productions are:
S→aABB/aAA
A→aBB/a
B→bBB/A Convert the given grammar to PDA that accept the same language by
empty
Stack.
Q24. Define Pushdown automata. Differentiate PDA by empty stack and final state by giving
their definitions.
Q25. Construct PDA for the language L = {a2nbn|n>=1}
Q26. Construct a deterministic pushdown automata to accept binary strings that start and end
with the same symbol and have same number of 0’s and 1’s.

Q27. Define a Pushdown Automata (PDA). Construct a PDA accepting the language of
Palindromes

Q28. . Show that if L is a language of Deterministic PDA and R is regular then LՈR is a
language of DPDA.
Q29. Describe the instantaneous description of a PDA
Q30. Consider the CFG whose productions are as follows:
S->aABB/aAA, A->aBB/a, B->bBB/A. Convert the given grammar to PDA that
accepts the same language by empty stack.

CO5

Q1. Construct Turing machine for L = {an bm) | n,m≥1}.

Q2. Construct a TM for the language L = {0n1n2n} where n≥1.
Q3. Construct TM for the addition function for the unary number system.
Q4. Design a Turing machine for 1’s and 2’s complement.
Q5) Differentiate between Recursive language and Recursively Enumerable Language
Q6. Explain PCP with suitable example.
Q7. Describe the necessary condition for Modified PCP Problem.
Q8. Define Halting Problem of Turing Machine.
Q9. Write short note on Church’s Thesis.
Q10. Write Short note on:
1) Variants of Turing Machine
2) Universal Turing Machine.
Q11. Explain Modified Post Corresponding Problem. Does the following Post
Corresponding Problem have a solution?
A= (101, 100, 10, 0, 010), B = (10, 01, 0, 100, 1)
Q12. Explain variations in Turing machine to make it more capable. How Universal
Turing machine can be considered as model of digital computer?
Q.13. Construct a Turing machine to accept the language L = {anbncm| m, n≥ 0}
Q14. Explain Church’s Thesis and prove that Halting problem of Turing machine is
undecidable.
Q15. Differentiate between Decidable and undecidable Problems with suitable example.
Q16. Construct Turing machine for any one of the following:
a) L= {anbm | n, m ≥ 1}.
b) L ={an+2bn | n >0 }