Finite Automata

2 Marks question
1. Distinguish between NFA and DFA.
2. Distinguish between Mealy and Moore Machines.
3. Applications of Mealy and Moore machines.
4. Applications and limitations of finite automata.
5. Discuss the different properties of transition function.
6. Determine the language generated by grammar having productions:
S→aS|A, A→bB|b, B→dC|˄, C→˄
7. Construct a DFA for the language over {0, 1}* such that it contains “000” as a substring.
8. Write RE for the languages of all Strings that do not end with 01.
9. Compare FA, NFA and NFA-^.

4 Marks question
1. Design a DFA with minimum number of states that recognizes the set of all binary strings
which contains four consecutive 1’s and give the formal description of the designed DFA.

2. Design a DFA equivalent to M=({q0 , q1 , q2}, {1, 0} , δ, q0 , {q2}) where the state diagram
for δ is given below: (4)

3. Construct deterministic finite automata to recognize odd number of 1’s and even number
of 0’s.
4. Design DFA to accept strings over ∑ = (0,1) with two consecutive 0’s.
5. Construct a Non-deterministic finite automata to accept strings containing the substring
0101.
6. Construct a DFA for the following: (a) All strings that contain exactly 4 zeros. (b) All
strings that don’t contain the substring 110.
7. Define regular expression. Prove that following regular expressions are equivalent.
a*(ab)*(a*(ab)*)* = (a+ab)*
10. Construct deterministic finite automata to recognize odd number of 1’s and even number of 0’s?
11. Convert the NFA given in Table below to its corresponding DFA and draw the DFA.

12. Convert the Mealy machine shown in given figure into Moore machine.

13. Figure shows NFA-^. Draw an FA accepting the same language.

12 Marks question
1. What do you mean by minimization of finite state automata? Construct a minimum state
automata equivalent to a automata given below:

2. What do you mean by equivalence of states in a Finite Automata? Construct a minimum

state automaton equivalent to Finite Automata with transition table given below: (12)
 States Input
0 1
→A B F
B A F
C G A
D H B
E A G
F H C
G A D
H A C

3. Construct a minimized DFA for the regular expression 10+(0+11)0*1

4. Construct a minimized DFA for the regular expression 1. (01 + 10)* + 0. (11 + 10)*.
5. Compare the Mealy and Moore machine? Define the characteristics of each. Transform
the following Mealy machine into Moore machine:

Present Next State

State
Input=0 Input=1
State Output State Output
q1 q3 0 q2 0

q2 q1 1 q4 0

q3 q2 1 q1 1

q4 q4 1 q3 1

Formal Languages
2 Marks question
1. Identify the languages generated by the following grammars.
a) S -> 0S1 | 0A1 A-> 1A | 1
b) S -> 0S1 | 0A1 A -> 1A0 | 10
2. Construct the grammar representing the set of palindromes over (0+1)*
 4 Marks question
1. Prove that each of the classes of languages is closed under union operation.

12 Marks question
1. What are the different types of languages as per Chomsky classification? Describe each
class in detail with the help of examples. Also prove that each class is closed under the
union, concatenation and transpose operation.

Regular Grammar
2 Marks question
1. Applications of regular expressions.
2. What do you mean by null production and unit production? Give an example.
3. Give a regular expression for the set of all strings having odd number of 1’s.
4. Give the regular expression for the set of all strings ending in 00.
5.

4 Marks question
1. Show that L = { ww | w € { a,b }* } is not regular using pumping lemma.
2. Construct a DFA with reduced states equivalent to the regular expression 10+(0+11)0*1
3. Prove that P + PQ* = a* bQ* where, P = b + aa*b and Q is regular expression.
4. Prove the following identity:
(a*ab + ba)* a* = (a + ab + ba)*
5. Find the regular expression corresponding to the given automata:
6. Construct an equivalent FA for the given regular expression (0+1)*(00+11)(0+1)*
7. Prove R=Q+RP has unique solution, R=QP*
8. Is regular set is closed under complementation? Justify.
9. Construct a grammar for set of strings that contain equal number of a’s and b’s over ∑ =
{a,b}
10. Construct the grammar representing the set of palindromes over (0+1)*
11. Derive the regular expression for the finite automata represented by following transition
diagram:

12. State Kleens Theorem. Construct the deterministic finite automaton equivalent to the
regular expression: ( a b ¿ ) (a+b)¿ ( b+ab)
13. Derive the regular expression for the following Transition Diagram

12 Marks question
Context Free Language
2 Marks question
1. Consider G whose productions are S-> S + S | S * S , S-> b | a. Show that S can derive
a*b+a*b and construct a derivation tree whose yield is a*b+a*b
2. Show that the grammar S-> aB | ab , A-> aAB | a , B-> ABb|b is ambiguous.
3. Remove the unit production from the grammar S->AB,A->E,B->C,C->D,D->b,E->a.
4. What are the type of productions in Griebach normal form?

5.

4 Marks question
1. Explain Greibach normal form in detail.
2. Construct a grammar in Greibach normal form equivalent to the grammar
S->AA , A-> SS | b.
3. Convert the grammar S-> AB, A-> BS | b, B-> SA | a into GNF.
4. Reduce the following CFG to GNF:
S-> ABb | a, A-> aaA, B-> bAb
5. What do you mean by ambiguity in context free grammars.
Show that a CFG G with productions S->SS | (S) | ^ is ambiguous.
6. Consider the following productions:
S-> aB | bA
A -> aS | bAA | a
B-> bS | aBB | b
For the string aaabbabbba, find
a) the leftmost derivation,
b) the rightmost derivation, and
c) the parse tree

7. Show that L = { ap | p is as prime} is not context free language using pumping lemma
8. Show that {anbncn | n>0} is not a context free language using the pumping lemma.
9. Explain the different steps for simplification of context free grammar. Take an example
grammar and simply it by applying the different steps for this process
10. Convert the following grammar G in greibach normal form.
S→ABb|a A→aaA|B B→bAb
 11. Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS , A-
> S1A | 10.
12. State and prove pumping lemma for CFL
13. Reduce the following grammar into Chomsky Normal form:
S→ab|aSC|BA,A→a|Cb|bb,B→aB|∈
14. Consider following grammar:

S -> ASB | Λ
A -> aAS | a
B -> SbS | A | bb
i. Eliminate useless symbols, if any.
ii. Eliminate Λ productions

12 Marks question
1. What is the purpose of normalization? Construct the CNF and
GNF for the following grammar and explain the steps.
S→aAa | bBb |€
A→C|a
B→C|b
C→CDE | €
D→A|B|ab

2. What you do mean by simplification of context free

grammar? How a grammar can be simplified? Find the
reduced grammar equivalent to the given grammar G, whose
productions are given below:
S → bA|aB , A → bAA|aS|a∨C , B → aBB|bs∨b , D → c

Push Down Automata

2 Marks question
1. PDA is more powerful than a finite automaton. Justify this statement.
 4 Marks question
1. Convert the grammar S-> aSb | A, A-> bSa | S | ^ to a PDA that accepts the same
language by empty stack.
2. Construct a Push Down Automata accepting {anb2n ǀ n≥1} by empty stack.
3. Construct a Push Down Automata accepting {ambn ǀ m>n≥1} by empty stack.

4. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.

5. What are the different ways of language acceptances by a PDA and define them?
6. Compare Deterministic and Non deterministic PDA. Is it true that non deterministic PDA
is more powerful than that of deterministic PDA? Justify your answer.
7. Prove that if there exists a PDA that accepts by final state then there exists an equivalent
PDA that accepts by Null state.
8. Construct an equivalent PDA for the following CFG
S->aAB | bBA
A->bS | a
B->aS | b
9. Convert the following PDA into an equivalent CFG.
δ (q0,a0,z0)->(q1,z1z0)
δ(q0,b,z0)->(q1,z2z0)
δ(q1,a,z1)->(q1, z1z1)
δ(q1,b,z1)->(q1, λ)
δ(q1,b,z2)->(q1,z2z2)
δ(q1,a,z2)->(q1, λ)
δ(q1, λ,z2)->(q1, λ) // accepted by the empty stack

12 Marks question
1. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.
2. Construct a Push Down Automata accepting {anbman ǀ m,n≥1} by empty stack. Construct
the corresponding context free grammar accepting the same set.

3. What is Push Down Automata? How is it different from a Finite Automata? Discuss the
acceptance of a string by Push Down Automata with the help of suitable examples.
 4. Construct a Push Down Automata accepting {anbman ǀ m,n≥1} by null store. Construct
the corresponding context free grammar accepting the same set.

Turing Machine, Context Sensitive Language

2 Marks question
1. What are the applications of Turing Machine?
2. State and prove the Post’s correspondence problem.
3. Discuss relation between LBA and CSL.
4. Define turing machine

4 Marks question
1. What is the purpose of a Turing Machine? Discuss Turing Machine in detail and also the
acceptability of strings by Turing Machine.

2. What are context sensitive languages? Discuss context sensitive languages in detail.

3. Design a Turing machine with no more than three states that accepts the language
a(a+b)*. Assume ∑ = {a,b}
4. What are the differences between a Finite automata and a Turing machine?
5. Explain the different models of Turing machines.
6. What is recursively enumerable language?
7. State when a problem is said to be decidable and give an example of an undecidable
problem.
8. What are context sensitive languages? Discuss context sensitive languages in detail.

9.

12 Marks question
1. Discuss the steps to design a Turing Machine. Design a Turing Machine that accepts the
language: L={1n2n3n|n≥1} (12)

2. Construct a Turing machine that recognizes the language L={anbn , n>1}. Show an ID for
the string ‘aabb’ with tape symbols.
3. How Turing machine is important in finding computation to different problems. Design a
Turing Machine to recognize all strings having an odd number of 1’s over {0,1}. Give the
Trace or Instantaneous description for w=0011010
4. Design the Turing machine to recognize the language: {an bn cn | n >=1}.
5. Design a PDA, M to accept L = { an b2n | n ≥ 1 }.
6. Define Push Down Automata (PDA). Design and draw a deterministic PDA
accepting strings with more a’s than b’s. Trace it for the string “abbabaa”.