TOAFL Question Bank

TOAFL (KCS 402)
QUESTION BANK
Short Question:
1. Prove or disprove the following regarding regular expressions:
i. (R + S)* = R* + S *
ii. (RS+R) *RS = (RR* S) *
2. (i) Convert the following CFG into CNF
S  Xy l xn l p
X  mX I m
YXn l o
(ii) Convert the following CFG into CNF
S  ASA l Ab
AB I S
B b l ε
3. Convert the FA given below to left linear grammer.

n n
4. Write CFG for language L = a b where n>=0. Also convert it into CNF.
5. Explain briefly about two stack PDA and differentiate it with single stack PDA.
6. Define halting problem of Turing machine.
7. Write a regular expression to denote a language L which accepts all the strings
that begin or end with either 00 or 11.
8. Convert the following CFG to its equivalent GNF: S → AA | a, A → SS | b.

i j k
9. Design a PDA for the following language: L = {a b c | i = j or j = k}
n n
10. Design a TM for the following language: L = { a +2b | n >0 }
11. For the given language L1 = ε, L2 = {a}, L3 = Ø. Compute L1 L2 * U L3 *
12. What is MyHillNerode theorem? How it is different from Arden’s Theorem.

Explain.
13. Prove that the compliment, homomorphism and inverse hornomorphism, closure
of a regular language is regular. Also State and prove kleene's theorem with an
example.
14. Define Context Free Grammar (CFG). Write the Context Free Grammar (CFG) for
regular expression (0+1)*
15. Design a DFA for languages L containing strings of 0 and 1’s where number of
0’s is not divisible by 3.
Long Question:
1. Construct a PDA M equivalent to grammar with following productions:
S a → AA, A → aS / / bS a Also, check whether the string ‘abaaaa’ is in M or

not.
2. What are various points of difference between Moore & Mealy Machine?
Explain the procedure to convert a moore machine into Mealy machine.
3. (i) Prove that the following Language L = {an bn : n>=0} is not a regular
language.
n n n
(ii) Design a Turing Machine for the language L. Where, L= {a b c | n≥1}
4. (a)Determine the language generated by grammar
S → Sab | aSb | abS| baS| bSa| Sba| aS| a
(b) What is inherent ambiguity? Explain with the help of suitable example.
5. (a) Design a PDA for the Language L ={WWR | W={a,b}* }
(b) Generate CFG for the given PDA M is defined as
M = ({q0, q1}, {0,1} {x, z0}, δ, q0, z0, q1) where δ is given as follows:
δ (q0,1, z0) = (q0, xz0)
δ (q0,1, x) = (q0, xx)
δ (q0,0, x) = (q0, x)
δ (q0, ε, x) = (q1, ε)
δ (q1, ε, x) = (q1, ε)
δ (q1,0, x) = (q1, xx)
δ (q1,0, z0) = ( q1, ε)
6. (a) Design a TM for the following language: L = { an+2 bn | n >0 }
(b) Explain in detail about the Pumping Lemma and application of Pumping
Lemma for Regular Languages
7. (a) Design the CFG for the following language:
(i) L = {0m1n | m ≠ n & m,n ≥ 1}
(ii) L = {al bmcn | l + m = n & l,m ≥ 1}
(b) Prove that the following Language L = {an bn cn } is not Context Free.
8. Write short notes on following.
(i) Turing Machine as Computer of Integer Functions
(ii) Universal Turing machine
9. (a) Minimize the following Automata:

(b) Convert the following NFA { p q, r, s}, {0,1},δ , p,{q, s} into DFA where δ is:
10. (i) Find the regular expression of Given FA using Arden’s theorem
(ii) Using pumping lemma for Regular languages prove that

language L = 0n^2, n >= 1 is not regular.
11. Explain Post Correspondence Problem. Let A = {1, 110, 0111} and B = {111,
001, 11} and  = {0, 1} Find the solution of PCP.
12. (a) Convert the following grammar in GNF: S → AB, A → BS / a, B → SA / b (b)

Define derivation Tree. Show the derivation tree for string ‘aabbbb’ with the
following grammar S→ AB/Є , A → aB, B → Sb
(c) Check whether the grammar is ambiguous or not. R-> R+R/ RR/ R*/ a / b / c.
Obtain the string w = a+b*c
13. Check with the comparison method for testing equivalence of two FA given
14. Design FA for the following languages containing binary strings:
(i) Having both 00 and 11 as substring.
(ii) Number of 0’s is odd and number of 1’s is multiple of 3
15. (i) State Arden’s theorem and construct regular expression for the following FA
using Arden’s theorem:
(ii) Design 2-stack PDA for language L: {anbncn I n>0}.

TOAFL Question Bank

Uploaded by

Copyright:

Available Formats

TOAFL Question Bank

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TOAFL Question Bank

Uploaded by

Copyright:

Available Formats

TOAFL (KCS 402)

ii. (RS+R) *RS = (RR* S) *

2. (i) Convert the following CFG into CNF

(ii) Convert the following CFG into CNF

3. Convert the FA given below to left linear grammer.

6. Define halting problem of Turing machine.

8. Convert the following CFG to its equivalent GNF: S → AA | a, A → SS | b.

11. For the given language L1 = ε, L2 = {a}, L3 = Ø. Compute L1 L2 * U L3 *

12. What is MyHillNerode theorem? How it is different from Arden’s Theorem.

S a → AA, A → aS / / bS a Also, check whether the string ‘abaaaa’ is in M or

4. (a)Determine the language generated by grammar

S → Sab | aSb | abS| baS| bSa| Sba| aS| a

5. (a) Design a PDA for the Language L ={WWR | W={a,b}* }

(b) Generate CFG for the given PDA M is defined as

δ (q0,1, z0) = (q0, xz0)

δ (q0,1, x) = (q0, xx)

δ (q1,0, x) = (q1, xx)

δ (q1,0, z0) = ( q1, ε)

6. (a) Design a TM for the following language: L = { an+2 bn | n >0 }

7. (a) Design the CFG for the following language:

(i) L = {0m1n | m ≠ n & m,n ≥ 1}

(ii) L = {al bmcn | l + m = n & l,m ≥ 1}

8. Write short notes on following.

(i) Turing Machine as Computer of Integer Functions

(ii) Universal Turing machine

9. (a) Minimize the following Automata:

(ii) Using pumping lemma for Regular languages prove that

12. (a) Convert the following grammar in GNF: S → AB, A → BS / a, B → SA / b (b)

14. Design FA for the following languages containing binary strings:

(i) Having both 00 and 11 as substring.

(ii) Number of 0’s is odd and number of 1’s is multiple of 3

(ii) Design 2-stack PDA for language L: {anbncn I n>0}.

You might also like

ii. (RS+R) RS = (RR S) *