K.S.

INSTITUTE OF TECHNOLOGY, BENGALURU - 560109

QUESTION BANK

2024-25(ODD)

Sem/Subject/Code: 5th/ TOC /BCS503

Module-1 Queston Bank

1. Make use of suitable examples to explain the following terms:
a. Alphabets
b. Strings
c. Empty Strings
d. Length of a string
e. Power of an alphabet
f. Concatenation of strings
g. Language
2. Identify the differences between DFA, NFA and ϵ-NFA with Examples.

3 . Design a DFSM to accept each of the following languages:

i). L= {wϵ{0,1}* : w has 001 as a substring}

ii). L={ aWa| W€(a+b)*}

iii). L={w | w is of even length and begins with 01}

iv). L={w:|w| mod 5< 3} where w €{a,b}*

v). L={wϵ{a,b}* :every a region in w is of even length.

vi) L={ wϵ{a,b}* : every a is immediately followed by b.

vii) L= {w: na(w)mod5 < 3 } where wϵ{a,b}*

4. Obtain a DFA to accept strings of a’s and b’s having

i) even number of a’s and even number b’s

ii) odd number of a’s and odd number of b’s
iii) even number of a’s and odd number b’s
iv) odd number of a’s and even number b’s
5. Construct a DFA which accepts a set of all binary strings divisible 3 or
binary strings divisible 5
6. Design a DFA to accept set of all strings on the alphabet ∑={0,1} that
either begins or ends or both with substring 01.

7. Design an NFA for the given keywords web and ebay and convert it into
DFA.

8. Design the NFA for the following transition table. q3 is final state q0
start state

9. Design an NFA with no more than 5 states for the following language.

L={ababn|n≥0} Ụ {aban|n≥0}

10.Construct the DFA for the following NFA using subset construction method.

Δ 0 1
->p {p,q} {p}
q {r} {r}
r {s} Ф
*s {s} {s}
11.Construct the DFA for the following NFA using lazy evaluation method.

12. Obtain the DFA for the following NFA using subset construction method

a,b

a b q2
q0 q1
13. Construct the DFA for the following NFA using Lazy method.

Δ 0 1
->q0 {q0, q1 } { q1}
*q1 { q2 } { q2 }
q2  { q2 }

14. Obtain the DFA for the following ϵ-NFA .

15. Obtain the DFA for the mentioned Epsilon NFA.

16. Obtain the DFA for the following ε-NFA .

states ε a b c
p Ф {p} {q} {r}
q {p} {q} {r} Ф
*r {q} {r} ф {p}

17. Show that A language L is accepted by some ∈-NFA if and only if L is accepted by
some DFA.
 18. Obtain the DFA for the following ∈-NFA

19. Prove that

Module-2 Queston Bank

1. Make use of the definition of Regular expression to explain the operators of RE.
2. Obtain the RE for the following languages
i.L={w€{a,b}* : w ending with string abb.
ii.L={w€{a,b}* :|w| is even}
iii.L={w€{0,1}*: w have 001 as a substring.
iv.L={ w€{0,1}*: w contains no consecutive 0’s
v. L={ w€{0,1}*: w contains at least two 0’s

3. Obtain the regular expressions for the following languages

a. The set of strings over alphabet {a,b,c} containing at least one a and at
least one b_
b. The set of strings of 0’s and 1’s whose tenth symbol from the right end is
a
c. The set of strings of 0’s and 1’s with at most one pair of consecutive 1’s.
 4. Build Regular expression from the FSM using the state elimination method

5. Obtain Regular Expression for the following finite automata

6. Build Regular expression from the FSM using the state elimination method

7.Obtain the Regular expression for the following languages.

a.L={anbmcp|n<=4,m>=2,p<=2}
b.L={w:|w|mod 3=0 w€{a,b}*}
c. L={anbm | m+n is even}
8. Build Regular expression from the following DFA

9. Obtain Regular Expression for the following finite automata

10. Obtain Regular Expression for the following finite automata

11. Obtain the FSM from the given RE

i. 00(0+1)*
ii. a*b*
iii. a*+b*+c*
iv.(a+b)*aa(a+b)*

11.State and prove pumping lemma for regular languages.

12.Explain the applications of pumping lemma.
13.Show that L={wwR |w€(0+1)*} is not Regular.
14. Show that L={an bn | n>=0 } is not Regular.
15. Show that L={ai bj | i>j } is not Regular.
16. Show that L={an! | n>=0 } is not Regular
17. Show that L={w|na(w)=nb(w)} is not Regular
18. Show that L={0n 1m 2n |n and m are arbitrary integers | is not Regular }
19.Explain the closure properties of Regular languages.
20.Obtain the Distinguishable table for the automata and then minimize the sates of the
following DFA using Table filling method

a b

A B F

B G C

*C A C

D C G

E H F

F C G

G G E

H G C

21. Find the minimized DFA for the following using Table filling method

0 1

A B A

B A C

C D B

*D D A

E D F

F G E

G F G

H G D

22. Find the minimized DFA for the following using Table filling method
23. Find the minimized DFA for the following using Table filling method

24. Find the minimized DFA for the following using Table filling method

25. Obtain the Distinguishable table for the automata and then minimize the sates of the
following DFA using Table filling method
 0 1

A B E

B C F

*C D H

D E H

E F I

*F G B

G H B

H I C

*I A E

26. Explain the applications of Regular expressions.

Module-3 Queston Bank

1.Make use of the definition of Context-free Grammar to construct the CFG for

a. L={anbn|n≥ 1}

b. L={w€{(, )}*} the parentheses are balanced.

c. L={w:|w| mod 3>0 where w€ {a}*

d. L={anb2n|n≥0}

e. L={wwR|w€{a,b}*]

f. L={anbncm|n,m≥1}

2. Obtain the grammar to generate string consisting of any number of a’s and b’s.

3. Obtain the grammar to generate strings of a’s and b’s such that string length is multiple of 3.

4.Make use of the definition of derivation to obtain the left most(LMD) and right most derivation
(RMD)for the given string id+id*id using below grammar

E->E+E|E-E|E*E|E/E|E^E|id

And also construct the parse tree.

5.Obtain the LMD and RMD for the given grammar using the string aabbab and check whether
the Grammar is ambiguous or not justify your answer.
S->aB|bA

A->aS|bAA|a

B->bS|aBB|b

6. Is the following grammar ambiguous? justify your answer by considering the input string
ibtibtaea.

S->iCtS|iCtSeS|a
C->b

7.Show that following grammar is ambiguous for the string aababb

S->aSbS
S->bSaS
S->€.

8. Make use of the definition of push down automata(PDA) to construct PDA for the following
language
L={anbn|n≥1}
and show the Instantaneous description (ID) for the input aaabbb.
9. Obtain the PDA for
L={wCwR|w€{a,b}* } and also validate the PDA by considering any input.
10. Construct a PDA for
L={wwR|w€{0,1}* } and also validate the PDA by considering any input.
11.Design a PDA for L={w:na(w)=nb(w)|n≥1} and write ID for aababb.
12.Design a PDA for L={anbncm|n,m≥1} and validate the PDA by considering any input.
13. Obtain the PDA for L={anb2n|n≥1} consider any input to write the ID.
14.For the grammar
S->aABC
A->aB|a
B->bA|b
C->a
Obtain the corresponding PDA and validate the same for the string aabba
15. For the grammar

S->aSb
S->ab
Obtain the PDA and validate the same by considering any input.
16. Convert the grammar
S->0S1|A
A->1A0|S|€
to a PDA that accepts the language by empty stack.
17. Convert the grammar to a PDA
 S->aAA
A->aS|bS|a.
18. Explain the languages of PDA.
19. Make use of the definition of Deterministic PDA to check whether the PDA corresponding to
the Language L={anbn|n≥1} is deterministic.
20. Make use of the definition of Deterministic PDA to check whether the PDA corresponding to
the Language L={ anb2n|n≥1} is deterministic

Module-4 Queston Bank

1.Eliminate useless symbols from the given grammar

S->aA|a|Bb|cc
A->aB
B->a|Aa
C->cDD
D->ddd

2.Eliminate useless symbols from the grammar

A->bA|Bba|aa
B->aBa|b|D
C->CA|AC|B
D->a|€

3.Eliminate €,Unit and useless productions

S->AaA|CA|BaB
A->aaBa|CDA|aa|DC
B->bB|bAB|bb|aS
C->Ca|bC|D
D->bD|€

4.Eliminate € productions

A->ABCa|bD
A->BC|b
B->b|€
C->c|€
D->d
5.Eliminate € productions

S->XYX
X->0X|€
Y->1Y|€

6.Eliminate Unit productions

S->AB
A->a
B->C|b
C->D
D->E|bC
E->d|Ab

7. Eliminate Unit productions

S->Aa|B|Ca
B->aB|b
C->Db|D
D->E|d
E->ab

8. Eliminate €,Unit and useless productions

S->AAA|B
A->aA|B
B->€.

9. Given the grammar

S->ASB|€
A->aAS|a
B->SbS|A|bb
• Are there any useless symbols?eliminate them if so.
• Eliminate €-productions
• Eliminate unit productions

10.Identify and explain the closure properties of Context-free languages.

11.Make Use of the definition of Pumping Lemma to explain pumping lemma for CFL.

12.Use the CFL pumping lemma to show each of these languages not to be context-free
 a)aibjck|i<j<k
b)anbnci|i<=n
c)0i1j|j=i2
d)anbnci|n<=i<=2n
13.Make use of the definition of CNF and convert the given CFG to CNF

S->aBa|abba
A->ab|AA
B->aB|a

14. Make use of the definition of CNF and convert the given CFG to CNF

S->0A|1B
A->0AA|1S|1
B->1BB|0S|0.

15. Make use of the definition of CNF and convert the given CFG to CNF

S->ABA
A->aA|€
B->bB|€

16. Make use of the definition of GNF and convert the given CFG to GNF

S->AA|0
A->SS|1

17.Make use of the definition of GNF and convert the given CFG to GNF

S->AB
A->BS|b
B->SA|a

Module-5 Question Bank.

1. Identify and explain the problems that computers cannot solve.
2. Define the Turing machine. Explain the working of a Turing machine.
3. Design a Turing machine to accept L={anbnCn |n>=1}.Draw the transition diagram. Show
the moves made by this Turing machine for the string aabbcc.
4. Write a note on the representation of the Turing machine.
5. Design a Turing machine and also construct a transition table for
 A)01* +10*
B) Palindrome(even length and odd length)
C) equal number of a’s and b’s
D) anbn|n>=1 Or 0n1n
E) Substring matching
F) Addition, subtraction and multiplication
G) L={w| w is even and ⅀={a,b}]
6. Explain the different techniques used for the construction of a TM
7. Explain the variants of the Turing machine.
8. Explain A Language that is not recursively enumerable.
9. Write a note PCP problem and Halting problem .