Tutorial Sheet 1
Course: B. Tech (CSE) 3rd year , Vth Sem Session: 2025-26
Subject Name & Code: Theory of Automata & Formal Languages (BCSC0011)
1. What is meaning of sentential form in CFG, explain it with the help of
proper example.
2. Write the CFG for given regular expression
a. r=0* 1(0+1) *
b. r = (a+b) *aa(a+b) *
3. Write a CFG, which generates palindrome for binary numbers (all
types odd and even).
4. Design a CFG for the language
L={anbm | n!=m}
5. Design CFG over input alphabet a and b that generates the set of
a. All strings with exactly one a.
b. All strings with least one a.
c. All strings with at least 3 a.
6. Calculate the followings terms in given grammar
E→ E+E
E→ E*E
E→id
W=id+id*id
a. Find out left most derivation.
b. Calculate the right most derivation.
c. Find out parse/derivation tree.
Also check above grammar, weather ambiguous or not.
7. Consider the CFG
S→XX
X→ XXX/bX/Xb/a
Find the parse tree for the string bbaaaab.
8. Consider the grammar G with the production
S→ aXY
B→ bYb
Y→ X/ ε
find the parse tree for the string abbbb.
9. Consider the CFG whose productions are
S→ aAS/a
A→ Sb/SS/ba
show that S⇒* aabbaa and construct a derivation tree whose yield is
aabbaa.
10. Let G be the CFG
S→ bB/aA
A→ b/bS/aAA
B→ a/aS/bBB.
For the string bbaababa find
[Link] derivation
[Link] derivation and
3. parse tree.
11. If CFG G is having following production rules show that G is ambigious
S→ Sb/S/a
12. Consider the productions for the if then else statement which are the p
art of the programming language
<statement > →
if<expression>then<st>|if<expression>then<st>else<st>else<st>| <other
statement>
expression → exp1| exp2|….exp.
<other statement>→ st1|st2|…….|stn.
13. Construct the grammar for the following languages.
1. L={aa,ab,ba,bb}
2. L={an | n>=1}
3. L=(a+b)*
4. L={set of all strings of length at leat two}
5. L={start with a and end with b}
6. L={start and end with different symbols}
7. L={anbn | n>=1}
8. L=WaWR
9. L={anbm |n,m>=1}
14. Consider the grammar having following production rules :
S→ aB/bA
A→ aS|bAA|a
B→ bS|aBB|b
for the string aaabbabbba find
(I) The leftmost derivation and leftmost derivation tree.
(II) The rightmost derivation and rightmost derivation tree.
[Link] that the grammar
S→ a|abSb|aAb
A→ bS|aAAb is ambigious.
16. Show that grammar
S→ aB|ab
A→ aAB|a
B→ Abb|b is ambigious
17. Consider the grammar with production
S→ aaB
A→ bBb|ε
B→ Aa
Show that the string aabbabba is not accepted by this grammar.
18. Give the derivation tree for (((a+b)(c))+a+b ,using the following grammar
E→ T
T→ F
F→ I
E→ E+T
T→ T*F
F→ (E)
I→ a|b|c.
19. Consider a CFG
S→ AB|a
A→ b
identify and eliminate the useless symbols.
20. Remove the useless symbol from the given context free grammar:
S→ aB|bX
A→ Bad | bSX |a
B→ aSB|bBX
X→SBD | aBx |ad
21. Consider the following grammar and obtain the equivalent grammar
containing no useless grammar symbol.
A→ xyx | Xyzz
X→ Xz |xYz
Y→ yYy | Xz
Z→ Zy |z.
[Link] the following grammar:
S→ aA
A→ b | ε remove the Nullable non-terminal
23. Consider the following grammar G
S→ ABAC
A→ aA |ε
B→ bB |ε
C→ c
remove the ε-production from the above grammar.
24. Consider the following grammar and remove the ε -productions
S→ aSa
S→bSb | ε
25. Consider the following grammar
S→ a | Xb|aYa
X→ Y | ε
y→ b | X
26. Change the following grammar in to CNF
S→ 1A | 0B
A → 1AA | 0S| 0
B → 0BB | 1
27. Change the following grammar in to CNF
G=({S},{a,b,c},{S→ a |b | CSS }, S)
28. Change the following grammar in to CNF
S→ abSb | a | aAb
A →bS | aAAb.
29. Convert CFG which is given below in to CNF form
S→ bA | aB
A→ bAA | aS | a
B→ aBB | bS| b.
30. Convert the grammar:
S→ AB | BC
A→ aB | bA | a
B → bB |cC | b
C→c
into GNF
31. Convert the grammar:
S→ abaSan |aba
into GNF.
32. Convert the grammar
S→AB
A→ BS | a
B→ SA | b
into GNF.
33. Convert the following grammar into GNF:
S→ aAS
S→ a
A→ SbA
A → SS
A→ ba.
34. Convert the following grammar G into GNF:
S→ XA | BB
B→ b | SB
X→ b
A→ a.
35. Construct a pda for the following CFG ,
G=(Vn, Vt, P,S) with Vn={S} ,Vt ={ (,)} and P is defined δ as follows:
S→ ε
S→ SS
S→ (S).
36. Construct a pda for the following CFG ,
G=(Vn, Vt, P,S) with Vn={S} ,Vt ={ a,b,c} and P is defined as follows:
S→ aSa
S→ bSb
S→ c.
37. For each of the CFG, construct PDA that accepts the same language they
generate
(1) S→ aSbb | abb
(2) S→ SS | a | b
(3) S→ XaaX
X→ aX | bX | ε
(4) S→ XY
X→ aX | bX| a
Y → Ya | Yb | a
(5) S→ Xa |Yb
X→ Sb | b
Y → Sa | a
38. Convert the following PDA into equivalent CFG.
1. δ(q0 ,a ,z0)→ ( q0 , z1z0)
2. δ(q0 ,a ,z1)→ ( q0 , z1z1)
3. δ(q0 ,b,z1)→ ( q1 , ε )
4. δ(q1 ,b ,z1)→ ( q1 , ε)
5. δ(q1 ,b ,z0)→ ( q1 , z2z0)
6.δ(q1 ,b ,z2)→ ( q1 , z2z2)
7. δ(q1 ,c ,z2)→ ( q2 , ε )
8. δ(q2 ,c ,z2)→ ( q2 , ε )
9. δ(q2 , ε ,z0)→ ( q2 , ε )
39. Consider the given PDA M=({q0}, {0,1}, {a,b,Z0}, δ, q0, Z0, Ø )
Where δ is defined as follows:
δ (q0 , 0, Z0)= {( q0, aZ0)}
δ(q0,1,Z0)={( q0, bZ0)}
δ (q0 , 0, a)= {( q0, aa)}
δ (q0 ,1, b)= {( q0, bb)}
δ (q0 , 0, b)= {( q0, ε)}
δ (q0 , 1, a)= {( q0, ε)}
δ (q0 , ε, Z0)= {( q0, ε)}
Convert the given PDA M to corresponding CFG.
40. Find equivalent CFG of the following given PDA:
PDA P= ({q0 , q1 } ,{a,b} ,{a, Z0 } ,δ ,q0 ,Z0)
where δ :
δ ( q0 ,a , z0) = (q0 , aZ0)
δ ( q0 ,a , a) = (q1 , aa)
δ ( q1 ,a , a) = (q1 , ε)
δ ( q1 , ε , Z0) = (q1 , ε)
Tutorial Sheet 2
Course: B. Tech (CSE 3rd year, Vth Sem Session: 2025-26
Subject Name & Code: Theory of Automata & Formal Languages (BCSC0011)
1. Consider the CFG
S→XX
X→ XXX/bX/Xb/a
Find the parse tree for the string bbaaaab.
2. Consider the grammar G with the production
S→ aXY
B→ bYb
Y→ X/ ε
find the parse tree for the string abbbb.
3. Consider the CFG whose productions are
S→ aAS/a
A→ Sb/SS/ba
show that S⇒* aabbaa and construct a derivation tree whose yield is aabbaa.
4. Let G be the CFG
S→ bB/aA
A→ b/bS/aAA
B→ a/aS/bBB.
For the string bbaababa find
[Link] derivation
[Link] derivation and
3. parse tree.
5. If CFG G is having following production rules show that G is ambigious
S→ Sb/S/a
6. Consider the productions for the if then else statement which are the p art of the
programming language
<statement > → if<expression>then<st>|if<expression>then<st>else<st>else<st>|
<other statement>
expression → exp1| exp2|….exp.
<other statement>→ st1|st2|…….|stn.
6. Construct the grammar for the following languages.
1. L={aa,ab,ba,bb}
2. L={an | n>=1}
3. L=(a+b)*
4. L={set of all strings of length at leat two}
5. L={start with a and end with b}
6. L={start and end with different symbols}
7. L={anbn | n>=1}
8. L=WaWR
9. L={anbm |n,m>=1}
7. Consider the grammar having following production rules :
S→ aB/bA
A→ aS|bAA|a
B→ bS|aBB|b
for the string aaabbabbba find
(I) The leftmost derivation and leftmost derivation tree.
(II) The rightmost derivation and rightmost derivation tree.
[Link] that the grammar
S→ a|abSb|aAb
A→ bS|aAAb is ambigious.
[Link] that grammar
S→ aB|ab
A→ aAB|a
B→ Abb|b is ambigious
10. Consider the grammar with production
S→ aaB
A→ bBb|ε
B→ Aa
Show that the string aabbabba is not accepted by this grammar.
11. Give the derivation tree for (((a+b)(c))+a+b ,using the following grammar
E→ T
T→ F
F→ I
E→ E+T
T→ T*F
F→ (E)
I→ a|b|c.
12. Consider a CFG
S→ AB|a
A→ b
identify and eliminate the useless symbols.
13. Remove the useless symbol from the given context free grammar:
S→ aB|bX
A→ Bad | bSX |a
B→ aSB|bBX
X→SBD | aBx |ad
14. Consider the following grammar and obtain the equivalent grammar containing no
useless grammar symbol.
A→ xyx | Xyzz
X→ Xz |xYz
Y→ yYy | Xz
Z→ Zy |z.
[Link] the following grammar :
S→ aA
A→ b | ε remove the Nullable non-terminal
16. Consider the following grammar G
S→ ABAC
A→ aA |ε
B→ bB |ε
C→ c
remove the ε-production from the above grammar.
17. Consider the following grammar and remove the ε -productions
S→ aSa
S→bSb | ε
18. Consider the following grammar
S→ a | Xb|aYa
X→ Y | ε
y→ b | X
19. Change the following grammar in to CNF
S→ 1A | 0B
A → 1AA | 0S| 0
B → 0BB | 1
20 . Change the following grammar in to CNF
G=({S},{a,b,c},{S→ a |b | CSS }, S)
21. Change the following grammar in to CNF
S→ abSb | a | aAb
A →bS | aAAb.
22. Convert CFG which is given below in to CNF form
S→ bA | aB
A→ bAA | aS | a
B→ aBB | bS| b.
23. Convert the grammar :
S→ AB | BC
A→ aB | bA | a
B → bB |cC | b
C→c
into GNF
24. Convert the grammar :
S→ abaSan |aba
into GNF.
25. Convert the grammar
S→AB
A→ BS | a
B→ SA | b
into GNF.
26. Convert the following grammar into GNF :
S→ aAS
S→ a
A→ SbA
A → SS
A→ ba.
27. Convert the following grammar G into GNF:
S→ XA | BB
B→ b | SB
X→ b
A→ a.
28. Construct a pda for the following CFG ,
G=(Vn, Vt, P,S) with Vn={S} ,Vt ={ (,)} and P is defined δ as follows:
S→ ε
S→ SS
S→ (S).
29. Construct a pda for the following CFG ,
G=(Vn, Vt, P,S) with Vn={S} ,Vt ={ a,b,c} and P is defined as follows:
S→ aSa
S→ bSb
S→ c.
30. For each of the CFG ,construct PDA that accepts the same language they generate
(1) S→ aSbb | abb
(2) S→ SS | a | b
(3) S→ XaaX
X→ aX | bX | ε
(4) S→ XY
X→ aX | bX| a
Y → Ya | Yb | a
(5) S→ Xa |Yb
X→ Sb | b
Y → Sa | a
31. Convert the following PDA into equivalent CFG.
1. δ(q0 ,a ,z0)→ ( q0 , z1z0)
2. δ(q0 ,a ,z1)→ ( q0 , z1z1)
3. δ(q0 ,b,z1)→ ( q1 , ε )
4. δ(q1 ,b ,z1)→ ( q1 , ε)
5. δ(q1 ,b ,z0)→ ( q1 , z2z0)
6.δ(q1 ,b ,z2)→ ( q1 , z2z2)
7. δ(q1 ,c ,z2)→ ( q2 , ε )
8. δ(q2 ,c ,z2)→ ( q2 , ε )
9. δ(q2 , ε ,z0)→ ( q2 , ε )
32. Consider the given PDA M=({q0}, {0,1}, {a,b,Z0}, δ, q0, Z0, Ø )
Where δ is defined as follows:
δ (q0 , 0, Z0)= {( q0, aZ0)}
δ(q0,1,Z0)={( q0, bZ0)}
δ (q0 , 0, a)= {( q0, aa)}
δ (q0 ,1, b)= {( q0, bb)}
δ (q0 , 0, b)= {( q0, ε)}
δ (q0 , 1, a)= {( q0, ε)}
δ (q0 , ε, Z0)= {( q0, ε)}
Convert the given PDA M to corresponding CFG.
33. Find equivalent CFG of the following given PDA:
PDA P= ({q0 , q1 } ,{a,b} ,{a, Z0 } ,δ ,q0 ,Z0)
where δ :
δ ( q0 ,a , z0) = (q0 , aZ0)
δ ( q0 ,a , a) = (q1 , aa)
δ ( q1 ,a , a) = (q1 , ε)
δ ( q1 , ε , Z0) = (q1 , ε)
Tutorial Sheet 3
Course: B. Tech (CSE) 3rd Year , V Sem Session: 2025-26
Subject Name & Code: Theory of Automata & Formal Languages (BCSC0011)
Q1. Write the comparative study (in tabular form) of DFA, PDA and TM along with
examples.
Q2. Design a TM to calculate 1’s complement of an input binary number.
Q3. Design a TM to calculate 2’s complement of an input binary number.
Q4. Design a TM to subtraction of two unary numbers i.e f(m,n)=m-n.
Q5. Construct a TM that accepts L= { anbn| n≥1}
Q6. Construct a Turing machine that can accept the set of all even palindromes over {0, 1}.
Q7. Construct a Turing machine that can accept the string over {0, 1} containing even
number of 1s.
Q8. Design a Turing machine that converts a binary string into its equivalent unary string.
Q9. Design a Turing machine to recognize the language L ={ anbncm |m, n≥1}.
Q10. Give an example of a language that is not recursive but recursively enumerable.
Q 11. Prove that there exists a Turing machine M for which the halting problem is
unsolvable.
Q 12. Compare computational power between deterministic TM and nondeterministic TM
using example.
Q13. Define variants of Turing Machine with the help suitable diagram
Q14. What do you understand by Universal Turing machine and Church Thesis.
Q15. Elaborate Recursive and Recursive Enumerable languages.
Q16. What is Halting Problem Explain in details.