Question Bank of Theory of Automata & Formal Languages
Long
Answer Question Bank
Theory of Automata & Formal Languages
UNIT 1
1. Find
closure of each state and give the set of all strings of length 3 or less
accepted by automaton.
2. Define
DFA, NFA & Language?
3. State and
prove Myhill Nerode Theorm
4. Design a
DFA to accept string of 0’s & 1’s when interpreted as binary numbers would
be multiple of 3
5. Find
closure of each state and give the set of all strings of length 3 or less
accepted by automaton.
6. Convert
following NFA to DFA using subset construction method
7. Write DFA
to accept strings of 0’s, 1’s & 2’s beginning with a 0 followed by odd
number of 1’s and ending with a 2.
8. Construct
DFA to accept the language of all strings of even numbers of a’s & numbers
of b’s divisible by three over (a+b)*.
9. Construct
the minimum state automata for the following : Initial State :A Final State: D
10. Design an
NFA for the following
i) L={
abaan | n≥ 1}
ii) To
accept language of all strings with 2 a’s followed by 2 b’s over {a,b}.
iii) To
accept strings with a’s and b’s such that the string end with bb.
UNIT
2
1. State and prove kleene’s theorem with
an example
2. P.T.
Let R be a regular expression. Then there exists a finite automaton M = (Q,¦,
G, q0, A) which accepts L(R).
3. Obtain a
regular expression to accept strings of a’s and b’s such that every block of
four consecutive symbols contains at least two a’s
4. Give
Mealy and Moore machines for the following processes:
a) For
input from (0 + 1)*, if the input ends in 101, output A; if the input ends in
110, output B; otherwise output C.
b) For
input from (0 + 1 + 2)*, print the residue modulo 5 of the input treated as a
ternary (base 3, with digits 0, 1, and 2) number.
5. Convert Regular
Expression 01* + 1 to Finite Automata.
6. Prove
that every language defined by a regular expression is also defined by Finite
Automata.
7. Write
Regular expression for the following
L = { an
bm : m, n are even}, L = { a n
,bm : m>=2, n>=2}.
8. Design a
Moore and Mealy machine to determine the residue mod 5 for each ternary string
(base 3) treated as ternary integer.
9. Obtain a
regular expression for the FA shown below:
10. Show that
following languages are not regular
a.
L={a nbm |
n, m t0 and nm }
b.
L={a nbm cm d n | n, m t1 }
c.
L={a n | n
is a perfect square }
d.
L={a n | n is a perfect cube }
UNIT
3
1. Find
out whether the language L = {xnynzn | n ≥ 1} is context free or not.
2. Discuss the Pumping lemma for
Context Free Languages concept with example
3. Check
whether the grammar is ambiguous or not.
R-> R+R/ RR/ R*/ a / b / c. Obtain
the string w = a+b*c
4. Convert
the following CFG into CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
5. Consider
the grammar with the production S->aSS A->b. Compute the string aababbb
with the left most and right most derivation. Draw the derivation tree.
6. Eliminate
unit productions in the grammar. S->A/bb A->B/b B->S/a.
7. Discuss
Ambiguity, left recursion and factoring in context free grammar.
8. Using
pumping lemma for CFL prove that below languages are not context free {p | p
is a prime}
9. a)
Explain Griebach Normal Form
b) i) Convert the following grammar
into GNF: EàE+T|T,
TàT*F|F,
Fà(E)|a.
ii) Convert the following grammar into GNF: àBa|ab,
AàaAB|a,
BàABb|b.
10. i)
Eliminate Null productions in the grammar SàABaC,
AèBC,
Bàb|ɛ,
CàD|ɛ,
Dàd.
ii)
Eliminate Unit productions in the grammar SàAB, Aàa, BàC, Bàb,CàD,DàE,Eàa.
iii) Find a reduced grammar equivalent
to the grammar G whose productions are
SàAB|CA,
BàBC|AB,
Aàa, CàaB|b.
UNIT 4
1.
Construct
PDA to accept L= {0n 1n | n > 0}
2.
Differentiate Deterministic PDA and Non-
Deterministic PDA.
3.
Define PDA.
Draw the graphical representation for PDA.
4.
Write the
procedure to convert from the given PDA to a CFG.
5.
Convert the
following example.
δ(q0,b,z0)={q0,zz0)
δ(q0,
b, z)=(q0,zz)
δ(q0,
ε ,z0)=(q0,ε)
δ(q0,a,z)
= (q1,z)
δ(q1,b,z)=(q1,ε)
δ(q1,a,z0)=(q0,z0)
6.
Construct a
PDA to accept the language L ={ a } by a final state. Draw the graphical
representation of the PDA.
Also
show the moves made by the PDA for the string aaabbb
7.
Design a PDA
to accept the set of all strings of 0’s and 1’s such that no prefix has more
1’s than 0’s
8.
Construct
PDA: Accepting the set of all strings over {a, b} with equal number of a’s and
b’s. Show the moves for abbaba.
9.
Construct
DPDA which accepts the language L = {wcwR | w {a, b}*, c Σ}.
10. Design a PDA which accepts set of
balanced paranthesis ( { { } } ).
11. Construct a PDA that accepts L = { wwR
| w = (a+b)* }
12. Construct a PDA from the following CFG.
G =
({S, X}, {a, b}, P, S) where the productions are −
S → XS
| ε , A → aXb | Ab | ab
UNIT
5
1.
Design a TM
to recognize all strings consisting of an odd number of α’s.
2.
Prove that
the halting problem is undecidable
3.
Prove that
single tape machines can simulate multi tape machines.
4.
Design a TM
to recognize all strings consisting of an odd number of α’s.
5.
Design a Turing machine to accept a Palindrome
6.
Define undesirability, decidability
7.
Post’s Correspondence problem Design a TM to
recognize a string of 0s and 1s such that the number of 0s is not twice as that
of 1s.
8.
P.t If L is a recursive language, L is also
recursive.
9.
Explain briefly the Halting problem
Comments
Post a Comment