QUESTION BANK

SUBJECT CODE : CSA13

SUBJECT NAME : THEORY OF COMPUTATION
BRANCH : CSE

UNIT – 1

S.No Question Marks

.
1 List some of the proving techniques in mathematics 2
2 Using Direct Proof, prove that If x ≥ 4 then 2 x ≥ x2 2
3 Disprove by counter example that “All primes are odd” 2
4 Disprove by counter example that If {a} ^ {2} = {b} ^ {2} , then a=b 2
5 Let L1={aab,bba} and L2={ab,ba}. Compute L1L2 and L1* 2
6 Let u and v be the strings u=abb and v=ba. Find 2
i) uv
ii) u R
iii) ¿ uv∨¿
iv) v 2
7 Define finite automata. What are the types of finite automata? 2
8 Write the formal definition of a finite automata with a description of each component. 2
9 Differentiate Deterministic and Non-Deterministic Finite Automata with an example. 2
10 List a few real-time applications of Finite Automata. 2
11 Find the language represented by the finite automata given below. Write 4 sample 2
strings that will be accepted by the automata.

12 Find the language represented by the finite automata given below. Write 4 sample 2
strings that will be accepted by the automata

13 Identify the language represented by the finite automata given below. Write 4 sample 2
strings that will be accepted by the automata
14 Find the language represented by the finite automata given below. Write 4 sample 2
strings that will be accepted by the automata

15 Find ε-closure for all the states for the ε-NFA given below. 2

16 Find ε-closure for all the states for the ε-NFA given below. 2

17 Consider the Deterministic Finite Automata whose transition table is given below. 2
Assume that q0 is the initial state and q2 is the final state. Check whether the input
‘abaab’ is accepted by the DFA.
State/Input a b
q0 q1 q0
q1 q1 q2
q2 q1 q0
18 Consider the Deterministic Finite Automata whose transition table is given below. 2
Assume that q0 is the initial state and q2 is the final state. Check whether the input
‘010100’ is accepted by the DFA.
State/Input 0 1
q0 q1 q0
q1 q2 q1
q2 q1 q2
19 Consider the Non Deterministic Finite automata given below. Write the formal 2
definition of the NFA.

20 Consider the Non Deterministic Finite automata given below. Check whether the 2
string ‘aabaa’ is accepted by the NFA by picturizing all possible transitions.
21 Prove by contradiction that √ 2 is irrational 5
22 Prove that for every integer n ≥ 0 , n3 +2 n is divisible by 3 5
23 Apply the principle of mathematical induction and prove that for all positive integers 5
n, the statement given below is true.
n
n(n+1)(2n+ 1)
∑ i 2= 6
i=1

24 Apply the principle of mathematical induction and prove that for all positive integers 5
n, the statement given below is true.
n(n+1)
1+2+3+…+ n=
2
25 Apply the principle of mathematical induction and prove that for all positive integers 5
n, the statement given below is true.
n 2 2
n (n+1)
∑i = 4
3

i=1

26 Design a Deterministic Finite Automata (DFA) that takes a binary string as input and 5
accepts the string only if the last two digits are the same (either 00 or 11). Write the
formal definition of the DFA. Also show that the string 10100 is accepted by the DFA
27 Design a Nondeterministic Finite Automata (NFA) that takes a binary string as input 5
and accepts the string only if the last two digits are the same (either 00 or 11). Write
the formal definition of the NFA. Also show that the string 01011 is accepted by the
NFA
28 Design a Deterministic Finite Automata (DFA) that accepts strings having ‘ab’ as a 5
substring over 𝚺={a,b}. Write the formal definition of the DFA. Also show that the
string aabaa is accepted by the DFA
29 Design a Nondeterministic Finite Automata (NFA) to accept strings that end with’ab’ 5
over 𝚺={0,1}. Write the formal definition of the NFA. Also show that the string
aabab is accepted by the NFA by picturizing all possible transitions
30 Construct a Deterministic Finite Automata (DFA) to accept strings having odd number 5
of 1’s over 𝚺={0,1}. Write the formal definition of the DFA. Also check whether the
string 010110 is accepted by the DFA or not.
31 Construct a Nondeterministic Finite Automata (NFA) to accept strings that end with 5
101 over 𝚺={0.1}. Write the formal definition of the NFA. Also show that the string
00101 is accepted by the NFA by picturizing all possible transitions
32 Design a Deterministic Finite Automata (DFA) to accept strings that start and end with 5
different symbols over𝚺={0,1}. Write the formal definition of the DFA. Also show
that the string 110100 is accepted by the DFA
33 Design a Nondeterministic Finite Automata (NFA) to accept strings that start and end 5
with different symbols over𝚺={0.1}. Write the formal definition of the NFA. Also
show that the string 110100 is accepted by the NFA by picturizing all possible
transitions
34 Design a Deterministic Finite Automata (DFA) to recognize the language containing 5
strings having at least three 1s over𝚺={0,1}. Write the formal definition of the DFA.
Also show that the string 110100 is accepted by the DFA
35 Design a Nondeterministic Finite Automata (NFA) to recognize the language 5
containing strings having at least three 1s over𝚺={0,1}. Write the formal definition of
the NFA. Also show that the string 110100 is accepted by the NFA by picturizing all
possible transitions
36 Consider the NFA given below which accepts some language L over the alphabet 10
𝚺={a,b}. Construct a DFA that represents the same language L

37 Consider the NFA given below which accepts the language representing the set of all 10
strings having 001 as a substring over the alphabet 𝚺={0,1}. Construct a DFA that
represents the same language

38 Consider the NFA given below which accepts some language L over the alphabet 10
𝚺={0,1}. Construct a DFA that represents the same language L

39 Consider the NFA given below which accepts some language L over the alphabet 10
𝚺={a,b}. Construct a DFA that represents the same language L

40 Consider the NFA given below which represents some language over the alphabet 10
𝚺={0,1}. Construct a DFA that represents the same language

41 A NFA with ε-transitions is given below. Find ε-closure for each state and construct 10
an equivalent NFA without ε-transitions that accepts the same language. Draw its
transition table and mark the initial and final states
 42 A NFA with ε-transitions is given below. Find ε-closure for each state and construct 10
an equivalent NFA without ε-transitions that accepts the same language. Draw its
transition table and mark the initial and final states

43 A NFA with ε-transitions is given below. Find ε-closure for each state and construct 10
an equivalent DFA which accepts the same language. Draw its transition table and
mark the initial and final states

44 A NFA with ε-transitions is given below. Find ε-closure for each state and construct 10
an equivalent DFA which accepts the same language. Draw its transition table and
mark the initial and final states

45 A NFA with ε-transitions is given below. Find ε-closure for each state and construct 10
an equivalent DFA that accepts the same language. Draw its transition table and mark
the initial and final states

UNIT – 2

S.No. Question Marks

1 What are regular languages? Give two examples. 2
2 Write the closure properties of regular languages with respect to union, concatenation, 2
intersection and complement operators.
3 Write closure properties of regular languages with respect to compliment, kleen star, 2
reversal and substitution
4 Formulate a regular expression for the language representing the set of all binary 2
strings having 101 as a substring
5 Write regular expression for the language containing strings that start and end with a 2
and any number of b’s in-between
6 Formulate a regular expression for the language representing the set of all strings that 2
start and end with the same symbol over 𝚺={a,b}.
7 Write regular expression to represent the language containing all strings over the set 2
{a,b} that end with aba or bb
8 Write regular expression to represent the set of all strings over the set {0,1} having 2
the substring 11 or 00
9 Formulate a regular expression for the language representing the set of all strings 2
with even number of a’s followed by odd number of b’s
10 Give an informal description of the language denoted by the regular expression 2
(0+1)*00
11 Give an informal description of the language denoted by the regular expression 2
a(a+b)*b+b(a+b)*a
12 Give an informal description of the language denoted by the regular expression 2
(a+b)*ab(a+b)*
13 Describe the language denoted by the regular expression (a+ab)* 2
14 Describe the language denoted by the regular expression (0+1) 1 (0+1)* 2
15 Describe the language denoted by the regular expression (0+10)*
16 If L1 and L2 are regular languages, what can you say about the following languages?
Are they regular?
i) L1 U L2
ii) L1*
iii) L1L2
iv) L1 Ո L2
17 If L1 is a regular language, what can you say about the following languages? Are they
regular?
i) Complement of L1
ii) Substitution of L1
iii) Homomorphism of L1
iv) Inverse homomorphism of L1
18 State pumping lemma for regular languages. 2
19 Define Arden’s Theorem. Where is it applied in automata theory? 2
20 What is the use of pumping lemma for regular languages? 2
2
21 Justify that the language L={0i ∨iis an integer ,i ≥1 } over the alphabet 𝚺={0} which 5
consists of all strings of 0’s whose length is a perfect square, is not regular using
pumping lemma
22 Justify that the language L consisting of all strings with an equal number of a’s and 5
b’s over the alphabet 𝚺={a,b} is not regular using pumping lemma
23 Justify that the language L= { ww|w ∈ ( 0+1 )∗}is not a regular language using pumping 5
lemma
24 Justify that the language L consisting of all strings over the alphabet 𝚺={a} whose 5
length is prime, is not regular using pumping lemma
2
25 Justify that the language L={a i ∨iis an integer ,i ≥ 1} over the alphabet 𝚺={a} which 5
consists of all strings of a’s whose length is a perfect square, is not regular using
pumping lemma
26 Justify that the language L consisting of all strings with an equal number of 0’s and 5
1’s over the alphabet 𝚺={0,1} is not regular using pumping lemma
27 Justify that the language L= { ww|w ∈ ( a+b )∗}is not a regular language using pumping 5
 lemma
28 Justify that the language L consisting of all strings over the alphabet 𝚺={1} whose 5
length is prime, is not regular using pumping lemma
29 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

30 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

31 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

32 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

33 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

34 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata
35 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

36 Apply Arden’s Theorem and derive the regular expression for the language 5
represented by the given automata

37 Consider the DFA given below. Find the states that are equivalent and construct a 10
minimum state automata equivalent to the given automata. Draw the minimized
automata, write its transition table and mark initial and final states

38 Consider the DFA given below. Find the states that are equivalent and construct a 10
minimum state automata equivalent to the given automata. Draw the minimized
automata, write its transition table and mark initial and final states
39 Consider the DFA given below. Find the states that are equivalent and construct a 10
minimum state automata equivalent to the given automata. Draw the minimized
automata, write its transition table and mark initial and final states

40 Consider the DFA given below. Find the states that are equivalent and construct a 10
minimum state automata equivalent to the given automata. Draw the minimized
automata, write its transition table and mark initial and final states
Next State
Present State
Input (a) Input (b)
s0 s0 s1
s1 s2 s0
s2 s1 s3
s3 s0 s3
s4 s5 s3
s5 s4 s6
s6 s6 s5
s7 s3 s6
41 Consider the DFA given below. Find the states that are equivalent and construct a 10
minimum state automata equivalent to the given automata. Draw the minimized
automata, write its transition table and mark initial and final states

42 Construct a non deterministic finite automata with ε-transitions to represent the 10

language denoted by the regular expression ab(a+b)*(ab)*
43 Construct a non deterministic finite automata with ε-transitions to represent the 10
language denoted by the regular expression (ab+ba)*abb
44 Construct a non deterministic finite automata with ε-transitions to represent the 10
language denoted by the regular expression 10+(0+11)0*1
45 Construct a non deterministic finite automata with ε-transitions to represent the 10
language denoted by the regular expression ab(a+b)*(ab)*
46 Construct a non deterministic finite automata with ε-transitions to represent the 10
language denoted by the regular expression (0+1)*00 + (0+1)*11
47 Construct a non deterministic finite automata with ε-transitions to represent the 10
language denoted by the regular expression 01(0+1)*(01)*
48 Construct a non deterministic finite automata with ε-transitions to represent the 10
 language denoted by the regular expression 00*1+11*0

UNIT – 3

S.No Question Marks

.
1 How do you call the languages represented by the type of automata listed below? 2
i) Finite Automata
ii) Pushdown Automata
iii) Linear Bounded Automata
iv) Turing Machine
2 Which type of automata/model can be used to accept the languages given below: 2
i) Regular Languages
ii) Context Free Languages
iii) Context Sensitive Languages
iv) Recursively Enumerable Languages

3 Formulate a Context Free Grammar for the language containing strings that start with 2
a and end with b over the alphabet set 𝚺={a,b}. Also, mention a few sample strings
in the language
4 Formulate a Context Free Grammar for the language containing strings that have 2
atleast one occurrence of 000 over the set 𝚺={0,1}. Also, mention a few sample
strings in the language
5 Formulate a Context Free Grammar for the language L={a n b 2 n∨n ≥1 } which 2
contains strings having n number of a’s followed by 2n number of b’s over the
alphabet set 𝚺={a,b}. Also, mention a few sample strings in the language
6 Formulate a Context Free Grammar for the language containing strings with 00 as a 2
substring over the alphabet set 𝚺={0,1}. Also, mention a few sample strings in the
language
7 Formulate a Context Free Grammar for the language containing strings having atleast 2
two a’s over the alphabet set 𝚺={a,b}. Also, mention a few sample strings in the
language
8 Formulate a Context Free Grammar for the language L={a n b n∨n ≥ 1} which contains 2
strings having n number of a’s followed by n number of b’s over the alphabet set
𝚺={a,b}. Also, mention a few sample strings in the language
9 Consider the grammar G=(V,T,P,S) where V={S,A},T={a,b} and P is the set of 2
productions given below. Find the language denoted by the given context free
grammar. Also, mention a few sample strings in the language
S → SAS |aS | bS | ε
A → aa
10 Consider the grammar G=(V,T,P,S) where V={S,A},T={a,b} and P is the set of 2
productions given below. Find the language denoted by the given context free
grammar. Also, mention a few sample strings in the language
S → aSbb | A
A → abb
11 Consider the grammar G=(V,T,P,S) where V={S,A},T={0,1} and P is the set of 2
productions given below. Find the language denoted by the given context free
 grammar. Also, mention a few sample strings in the language
S → 0A1 | 1A0
A → 0A | 1A | ε
12 Consider the grammar G=(V,T,P,S) where V={S, A, T},T={0,1} and P is the set of 2
productions given below. Find the language denoted by the given context free
grammar. Also, mention a few sample strings in the language
S → ATA
A → 0A | 1A | ε
T → 000
13 Consider the grammar G=(V,T,P,S) where V={S},T={a,b} and P is the set of 2
productions given below. Find the language denoted by the given context free
grammar. Also, mention a few sample strings in the language
S → aSa | bSb | a | b | ε
14 Consider the grammar G=(V,T,P,S) where V={E},T={ + , * , ( , ) , id } and P is the 2
set of productions given below. Find the language denoted by the given context free
grammar. Also, mention a few sample strings in the language
E → E+E | E*E | (E) | id
15 Compare the closure properties of regular languages and context free languages with 2
respect to the following operators.
i) Union
ii) Intersection
iii) Compliment
iv) Concatenation
16 If L1 and L2 are two context free languages, what can you say about the languages 2
given below? Are they context free?
i) L1UL2
ii) L1∩L2
iii) L1*
iv) L1 L2
17 If L1 and L2 are two context free languages, what can you say about the languages 2
given below? Are they context free?
v) Compliment of L2
vi) L1∩L2
vii) Substitution of L1
viii)Homomorphism of L2
18 What is an ambiguous grammar? Give an example. 2
19 List the two normal forms for writing Context Free Grammar. 2
20 State pumping lemma for context free languages. 2
21 Tabulate the different types of grammar in Chomsky’s hierarchy, the language 5
accepted be each grammar and the corresponding automata
22 Justify that the language {0 n 1n 2n∨n ≥ 1} over the alphabet 𝚺={0,1,2} is not context 5
free using pumping lemma
23 Justify that the language {0i 1 j 2i 3 j∨i , j ≥1 } over the alphabet 𝚺={0,1,2,3} is not 5
context free using pumping lemma
24 Justify that the language {0i 1 j 2k ∨i< j< k } over the alphabet 𝚺={0,1,2} is not context 5
free using pumping lemma
25 Justify that the language {a p∨ p is prime } over the alphabet 𝚺={a} is not context free 5
 using pumping lemma
26 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string ((a,a),(a,a)) from the given grammar
S → (L) | a
L → L, S | S
27 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string aabbbb from the given grammar
S → aSbb | A
A → abb
28 Consider the following Context Free Grammar 5
S → aB | bA
A→a | aS | bAA
B→b | bS | aBB
For the input string abbaab find
a) Leftmost Derivation
b) Rightmost Derivation
c) Parse Tree
29 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string 1000111 from the given grammar.
S → T00T
T → 0T | 1T | ℇ
30 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string 00110101 from the given grammar
S → 0B | 1A
A → 0 | 0S | 1AA
B → 1 | 1S | 0BB
31 Consider the following Context Free Grammar 5
S → aAS
S→ a
A→ SbA
A→ SS
A→ ba
For the input string aabbaa find
a) Leftmost Derivation
b) Rightmost Derivation
c) Parse Tree
32 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string ababbb from the given grammar
S → AB |ε
A → aB
B → Sb
33 Write leftmost, rightmost derivations and depict the corresponding parse tree for the 5
string babba from the given grammar
S → Aa | bB | ℇ
A → bS |ℇ
B → aA
34 Consider the following Context Free Grammar 5
S→AB | 0
 A→BC | 1
B→CD | 2
C→AD | 0
D→1
For the input string 01112 find
a) Leftmost Derivation
b) Rightmost Derivation
c) Parse Tree
35 Consider the grammar G=(V,T,P,S) where V={S},T={a,b} and P is the set of 5
productions given below. Find the symbols which are nullable and eliminate ε-
productions from the grammar
S → Aa | bB | ε
A → bS |ε
B → aA
36 Consider the grammar G=(V,T,P,S) where V={E,T,F}, T={ +, *, (, ), id } and P is the 5
set of productions given below. Write all unit pairs and rewrite the grammar without
unit productions
E → E+T | T
T → T*F |F
F → ( E ) | id
37 Find the symbols that are not generating and not reachable. Analyze the context free 5
grammar given below and eliminate such useless symbols from the grammar if
present
S → AS | 1SA | BS | 2
A → 0BC | 1
B→C
C → 0C | 0
D→0|2
38 Optimize the grammar given below by eliminating ε-productions, unit productions 5
and useless symbols
S → aAA | ε
A → aS | bS | ε

39 Optimize the grammar given below by eliminating ε-productions, unit productions 5

and useless symbols
S → 0S1 | A
A → 1A0 | S | ε
40 Optimize the grammar given below by eliminating ε-productions, unit productions 5
and useless symbols
S → 0A | 1BB | 0S
A → 1 | 0B | ε
B → 1S | 1 | ε

41 Consider the grammar G=(V,T,P,S) where V={S},T={a,b} and P is the set of 5

productions given below. Find the symbols which are nullable and eliminate ℇ-
productions from the grammar
S → aSa | bSb | a | b | ε
42 Consider the grammar G=(V,T,P,S) where V={S,A,B,C}, T={0,1} and P is the set of 5
 productions given below. Write all unit pairs and rewrite the grammar without unit
productions
S → 0A | 1B | C
A → 0S | 00
B→1|A
C → 01
43 Find the symbols that are not generating and not reachable. Analyze the context free 5
grammar given below and eliminate such useless symbols from the grammar if
present
S → B|A
A → aA|E
B → bB|b
E → Ea|C
C→b
44 Consider the grammar G=(V,T,P,S) where V={S, A, T},T={0,1} and P is the set of 5
productions given below. Find the symbols which are nullable and eliminate ℇ-
productions from the grammar
S → ATA
A → 0A | 1A | ε
T → 000
45 Consider the grammar G=(V,T,P,S) where V={S,A,B,D}, T={a,b,c} and P is the set 5
of productions given below. Write all unit pairs and rewrite the grammar without
unit productions
S → Aa | B
B → A |cc
A→D
D → a| bc | B

46 Find the symbols that are not generating and not reachable. Analyze the context free 5
grammar given below and eliminate such useless symbols from the grammar if
present
S → AB|CA
A→a
B → BC|AB
C → aB |b
D → aA|d

47 Rewrite the grammar in Chomsky Normal Form (CNF). If needed, optimize the 10
grammar before rewriting
S → ATA
A → 0A | 1A | ε
T → 000
48 Rewrite the grammar in Chomsky Normal Form (CNF). If needed, optimize the 10
grammar before rewriting
S → Aa | bB | ε
A → bS | ε
B → aA
49 Rewrite the grammar in Chomsky Normal Form (CNF). If needed, optimize the 10
 grammar before rewriting
S → SAS |aS | bS | ε
A → aa
50 Rewrite the grammar in Chomsky Normal Form (CNF). If needed, optimize the 10
grammar before rewriting
E → E+T | T
T → T*F | F
F → (E) | I
I → Ia | Ib | I0 | I1 | a | b
51 Rewrite the grammar in Chomsky Normal Form (CNF). If needed, optimize the 10
grammar before rewriting
S → (L) | a
L → L,S | S
52 Optimize the given Context Free Grammar if needed and put the resulting grammar in 10
Greibach Normal Form (GNF)
S → AB
A → BS | b
B → SA | a
53 Optimize the given Context Free Grammar if needed and put the resulting grammar in 10
Greibach Normal Form (GNF)
S →ABA
A →aA |ℇ
B→bB |ℇ
54 Optimize the given Context Free Grammar if needed and put the resulting grammar in 10
Greibach Normal Form (GNF)
S → XY
X → YS | a
Y → SX | b
55 Optimize the given Context Free Grammar if needed and put the resulting grammar in 10
Greibach Normal Form (GNF)
S → CA | BB
B → b | SB
C→b
A→a
56 Optimize the given Context Free Grammar if needed and put the resulting grammar in 10
Greibach Normal Form (GNF)
S→A | 0C1
A→B | 01 | 10
C→ CD | ε

UNIT – 4

S.No. Question Marks

1 Write the formal definition of a Pushdown Automata 2
2 What is a pushdown automata? In what way it is different from finite automata? 2
3 What are the two ways of designing a pushdown automata? 2
4 Does a Pushown Automata have memory? If so, what is the approximate capacity of 2
 its memory?
5 Differentiate acceptance by empty stack and acceptance by final state in a pushdown 2
automata.
6 Write a few applications of context free grammar and pushdown automata. 2
7 Define Instantaneous Description of a Pushdown Automata. 2
8 Is Non Deterministic Pushdown Automata (NPDA) and Deterministic Pushdown 2
Automata (DPDA) equivalent?
9 List the different programming techniques that can be used in designing turing 2
machines.
10 Write a short note on subroutines in turing machines 2
11 What is a turing machine? Whether a turing machine can be designed to compute 2
functions or it can be used only for recognizing languages?
12 Draw the turing machine model with multiple tracks. 2
13 How turing machine with multiple tracks can be used for checking off symbols. 2
14 Who invented Turing Machine? Draw the structure of a Basic Turing Machine 2
15 List the components in the formal description of a Turing Machine. 2
16 Does a Turing Machine have memory? If so, which acts as its memory and what is 2
the approximate capacity of its memory?
17 Write a note on Storage in Finite Control in Turing Machines. 2
18 How do you call the languages represented by the type of automata listed below? 2
i) Pushdown Automata
ii) Turing Machine
19 Differentiate Pushdown Automata and Turing Machine 2
20 Compare Finite Automata, Pushdown Automata and Turing Machine 2
21 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → (L) | a
L → L, S | S
22 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → ATA
A → 0A | 1A | ε
T → 000
23 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
E→E+T|T
T→T*F|F
F → ( E ) | id
24 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → aB | bA
A→a | aS | bAA
B→b | bS | aBB
25 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S→AB | 0
A→BC | 1
B→CD | 2
C→AD | 0
D→1

26 Consider the context fee grammar given below. 5

Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → 0B | 1A
A → 0 | 0S | 1AA
B → 1 | 1S | 0BB
27 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → XY
X → YS | a
Y → SX | b
28 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S → CA | BB
B → b | SB
C→b
A→a
29 Consider the context fee grammar given below. 5
Convert the CFG to a Pushdown Automata that accepts by empty stack. Write the
formal definition of the PDA.
S→A | 0C1
A→B | 01 | 10
C→ CD | ε

30 Design a Pushdown Automata for the language representing a’s followed by b’s and 5
the number of a’s and b’s must be the same.
n n
L={a b ∨n ≥1 }
Write the logic for the design and the formal definition.
31 Design a Pushdown Automata for the language representing 0’s followed by 1’s and 5
the number of 0’s and 1’s must be the same.
n n
L={0 1 ∨n ≥ 1}
Write the logic for the design and the formal definition.
32 Design a Pushdown Automata for the language representing a’s followed by b’s and 5
the number of b’s must be twice than that of a’s.
n 2n
L={a b ∨n≥ 1 }
Write the logic for the design and the formal definition.
33 Design a Pushdown Automata for the language representing 0’s followed by 1’s and 5
 the number of 1’s must be twice than that of 0’s.
n 2n
L={0 1 ∨n ≥1 }
Write the logic for the design and the formal definition.
34 Design a Pushdown Automata for the language representing strings having equal 5
number of 0’s in the front and the back and any number of 1’s in between.
n m n
L={0 1 0 ∨n ≥ 1}
Write the logic for the design and the formal definition.
35 Design a Pushdown Automata for the language representing strings having equal 5
number of a’s in the front and the back and any number of b’s in between.
n m n
L={a b a ∨n ≥ 1}
Write the logic for the design and the formal definition.
36 Convert the Pushdown Automata given below to a Context Free Grammar. 10
M=({s0,s1},{a,b},{Z0,a},δ,s0,Z0,ϕ) where δ is defined as
δ(s0,a,Z0)={(s0,aZ0)}
δ(s0,a,a)={(s0,aa)}
δ(s0,b,a)={(s1,ε)}
δ(s1,b,a)={(s1,ε)}
δ(s1,ε,Z0)={(s1,ε)}
37 Convert the Pushdown Automata given below to a Context Free Grammar. 10
M={q0,q1},{0,1},{X,Z0},δ, q0,Z0} where δ is defined as
δ(q0,0,Z0)={(q0,XZ0)}
δ(q1,1,X)={(q1,ℇ)}
δ(q0,0,X)={(q0,XX)}
δ(q1,ℇ,X)={(q1,ℇ)}
δ(q0,1,X)={(q1,ℇ)}
δ(q1,ℇ,Z0)={(q1,ℇ)}

38 Convert the Pushdown Automata given below to a Context Free Grammar. 10

M={s0,s1},{0,1},{X,Z0},δ, s0,Z0} where δ is defined as
δ(s0,1,Z0)={(s0,XZ0)}
δ(s0,1,X)={(s0,XX)}
δ(s0,0,X)={(s1,X)}
δ(s0, ε,X)={(s0, ε)}
δ(s1,1,X)={(s1, ε)}
δ(s1,0,Z0)={(s0, Z0)}
39 Design a Pushdown Automata for the language representing 0’s followed by 1’s and 10
the number of 0’s and 1’s must be the same.
n n
L={0 1 ∨n ≥ 1}
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string ‘000111’.
40 Design a Pushdown Automata for the language representing a’s followed by b’s and 10
the number of b’s must be twice than that of a’s.
n 2n
L={a b ∨n≥ 1 }
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string ‘aabbbb’.
41 Design a Push Down Automata that accepts the language 10
L= { w|w ∈ ( a+b )∗¿ n a ( w ) >n b (w)}
 n a ( w ) is the number of a’s in w
n b (w) is the number of b’s in w
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string
‘abbaaaab’.
42 Design a Push Down Automata that accepts the language 10
L= { w|w ∈ ( a+b )∗¿ n a ( w )=nb (w)}
n a ( w ) is the number of a’s in w
n b (w) is the number of b’s in w
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string ‘abbaab’.
43 Design a Push Down Automata that accepts the language 10
L= { w|w ∈ ( 0+1 )∗¿ n0 ( w ) > n1 (w)}
n 0 ( w ) is the number of 0’s in w
n1 (w) is the number of 1’s in w
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string
‘01100001’.
44 Design a Push Down Automata that accepts the language 10
L= { w|w ∈ ( 0+1 )∗¿ n0 ( w ) =n1 (w) }
n 0 ( w ) is the number of 0’s in w
n1 ( w) is the number of 1’s in w
Write the logic for the design and the formal definition. Also show all reachable
Instantaneous Descriptions (ID’s) starting from the initial ID for the string
‘01100001’.
45 Consider the language L= { 0n 1 n 2n|n ≥ 1}. Design a basic turing machine for the 10
language. Explain the logic used for the design and write its formal definition.
46 Construct a Turing Machine to recognize the language 10
n n
L={a b ∨n ≥1 }
Write the logic used for the design and the formal definition
47 Construct a Turing Machine to recognize the language 10
n n
L={0 1 ∨n ≥ 1}
Write the logic used for the design and the formal definition
48 Construct a Turing Machine to recognize the language 10
n 2n
L={a b ∨n≥ 1 }
Write the logic used for the design and the formal definition
49 Construct a Turing Machine to recognize the language 10
n n n
L={a b c ∨n≥ 1 }
Write the logic used for the design and the formal definition
50 Construct a Turing Machine to recognize the language 10
L= { 0 1 |n ≥ 1}
n 2n

Write the logic used for the design and the formal definition

UNIT – 5

S.No. Question Marks

1 Define recursive language. Give two examples. 2
2 Define recursively enumerable language. Give two examples 2
3 What is a universal language? Is it decidable? Is it recursive enumerable? 2
4 What is halting problem of Turing Machine? Is it decidable? 2
5 What is a decidable problem? Give two examples. 2
6 What is an undecidable problem. Give two examples. 2
7 What is a universal turing machine? Is the language defined by a universal turing 2
machine recursive?
8 Define diagonalization language Ld. 2
9 List any four properties of recursive languages. 2
10 If L1 and L2 are recursively enumerable languages, what can you say about the 2
languages given below? Are they recursively enumerable?
i) L1UL2
ii) L1∩L2
11 If L1 and L2 are recursive languages, what can you say about the languages given 2
below? Are they recursive?
i) L1UL2
ii) L1∩L2
12 If L1 is a recursively enumerable language, what can you say about the languages 2
given below? Are they recursively enumerable?
i) Inverse homomorphism of L1
ii) Complement of L1
13 If L1 is a recursive language, what can you say about the languages given below? 2
Are they recursive?
i) Inverse homomorphism of L1
ii) Complement of L1
14 Define Post Correspondence Problem (PCP). 2
15 Is Post Correspondence Problem (PCP) decidable? Give an application of PCP. 2
16 State Rice’s Theorem for property of languages. 2
17 What properties of recursively enumerable sets are not decidable? 2
18 What are the concepts used in Universal Turing Machines? 2
19 What are the possibilities of halting when a turing machine processes an input string? 2
20 What are the applications of Turing Machine? 2
21 Differentiate recursive and recursively enumerable languages with suitable examples. 5
22 Differentiate decidable and undecidable problems with suitable examples. 5
23 Prove that the universal language Lu is recursively enumerable 5
24 Write short notes on diagonalization language Ld. Is it recursively enumerable? 5
25 List all the properties of recursive and recursively enumerable languages. 5
26 Prove the following: 5
i) Union of two Recursively Enumerable Languages is Recursively
Enumerable
ii) Union of two Recursive Languages is Recursive
27 Prove the following: 5
i) Intersection of two Recursively Enumerable Languages is Recursively
Enumerable
ii) Intersection of two Recursive Languages is Recursive
28 Prove the following: 5
i) Complement of a Recursive Languages is Recursive
 ii) Intersection of two Recursively Enumerable Languages is Recursively
Enumerable
29 List all the properties of recursive languages and prove the following: 10
i) Union of two Recursive Languages is a Recursive Language
ii) Intersection of two Recursive Languages is a Recursive Language
iii)Complement of a Recursive Language is Recursive
30 Explain how a Turing Machine is represented in binary format using Turing Machine 10
Codes with an example.
31 Write short notes on Turing machine codes. 10
Encode the Turing Machine whose description is given below in binary
representation.
T = ({s0, s1}, {0,1}, {0,1,B}, δ(s0,0)=(s0,0,R), δ(s0,1)=(s0,1,R), δ(s0,B)=(s1,1,L), s0, B,
s1}

32 Write short notes on Turing machine codes. 10

Encode the Turing Machine whose description is given below in binary
representation.
T = ({q0, q1}, {0,1}, {0,1,B}, δ(q0,0)=(q0,0,R), δ(q0,1)=(q0,1,R), δ(q0,B)=(q1,1,L), q0,
B, q1}

33 Write short notes on Turing machine codes. 10

Encode the Turing Machine whose description is given below in binary
representation.
T = ({q0, q1, q2}, {0,1}, {0,1,B}, δ(q0,0)=(q0,0,R), δ(q0,1)=(q0,1,R), δ(q1,0)=( q1,0,R),
δ(q1,1)=( q1,1,R), δ(q0,B)=(q1,1,L), q0, B, q2}

34 Write short notes on Turing machine codes. 10

Encode the Turing Machine whose description is given below in binary
representation.
T = ({s0, s1,s2}, {0,1}, {0,1,B}, δ(s0,0)=(s0,0,R), δ(s0,1)=(s0,1,R), δ(s1,0)=(s1,0,R),
δ(s1,1)=(s1,1,R), δ(s0,B)=(s1,1,L), s0, B, s2}

35 What is Post Correspondence Problem (PCP)? Apply PCP for the dominos given 10
below.

{
ab ba b abb a
, , ,
aba abb ab b bab
, }
36 What is Post Correspondence Problem (PCP)? Apply PCP for the dominos given 10
below.

{
1 0 20 012
, , ,
20 01 0 2 }
37 What is Post Correspondence Problem (PCP)? Apply PCP for the dominos given 10
below.

{
B A CA ABC
,
CA AB A
, ,
C }
 UNIT VI

S.No. Question Marks

1 Define Time and Space Complexity 2
2 List out the types of complexity classes 2
3 What is tractable problems 2
4 What is intractable problems 2
5 List out the Types of Problems 2
6 Mention the difference between P and NP problems 2
7 StateNP-hard problems 2
8 What is NP-complete problems. 2
9 Difference between tractable and intractable problems 2
10 Differentiate NP-complete and NP-hard problems 2
11 List out the types of TM 2
12 List out the types of algorithm 2
13 Explain tractable and intractable problems with suitable examples. 5
14 Explain the types of Turing Machine with suitable examples. 5
15 Explain the classes of P and NP with suitable examples. 5
16 Explain class P problem with example 5
17 Explain types of algorithm with suitable examples. 5
18 What is 3 sat Problem? Solve 3 sat Problem in polynomial time 10
19 What is Vertex Cover Problem? Solve Vertex Cover Problem in polynomial time 10

20 Apply non deterministic Turing Machine to solve class NP Problem with polynomial time 10
complexity
21 Outline the concept of polynomial time reductions 10
22 What are tractable problems? Compare it with intractable problems 10