Theory of Computation : End Sem Examination ( 4th Sem )

 Theory Of Computation

End Semester Examination, 2021-22
B. Tech - Semester : 04
Time : 03 hrs. - Max. Marks : 100

Instructions:

1. All questions are Compulsory
2. Assume missing data suitably, if any.

Section : A ( 10 x 4 = 40 Marks )

All questions are compulsory

1. Define nondeterministic finite automata (NFA). Draw the NFA for the language L={an b m | n, m >=1}.
2. Convert the following NFA to DFA.
3. Construct regular expression for the language that consists of all strings ending with 00. Assume ⅀={0, 1}.
4. Differentiate Moore machine from Mealy machine. Write the tuple representation for both machines.
5. Whether the following grammar is ambiguous?
   E-> E+E| E*E|I
   I-> 0|1|a|b
   For string w= a+b*a
6. Prove that the following Language L = { a^n b^n c^n } is not Context Free.
7. Define derivation Tree. Show the derivation tree for string 'aabbbb' with the following grammar S->AB/∈, A->ab, B->Sb.
8. Define a deterministic PDA. How a DPDA differs from a non-deterministic PDA?
9. Explain the concept of Turning Machine? Give the representation of a Turning machine.
10. Write a short note on Halting Problem Of Tuning Machine.

Section : B ( 3 x 6 = 18 Marks )

All questions are compulsory

1. Eliminate the unit Production from the given Grammar-
   S→Ab/B/a, A→bB/S, B→aAb/b
   OR
   Reduce the given CFG to Greibach normal form S→AB, A→BSB, A→BB, B→aAb
2. Design a DPDA for the language L ={WcW^R | W={a,b,c}+ }.
   OR
   Design a NDPDA for the language L ={WW^R | W={a,b}+ }.
   
3. Define PCP. Let A = {1, 110, 0111} and B = {111, 001, 11} and ⅀ = {0, 1}. Find the solution of PCP.
   OR
   Write short note on: i) Universal Turning Machine. ii) PCP Problem and Modified PCP Problem.

Section : C ( 3 x 10 = 30 Marks )

All questions are compulsory

1. Write the procedure to convert a given CFG into equivalent grammar in CNF. Apply the procedure and convert the grammar with following production into CNF: S→bA|aB, A→bAA|aS|a, B→aBB|bS|b.
   OR
   Let G be the grammar S→0B|1A, A→0|0S|1AA, B→1|1S|0BB
   For the string 00110101, find:
   (i) The leftmost derivation.
   (ii) The rightmost derivation.
   (iii) The derivation tree.
2. Construct a PDA M equivalent to grammar with following productions:
   S→aAA, A→aS / bS / a
   Also, check whether the string 'abaaaa' is in M or not.
   OR
   Prove the equivalence of acceptance of a PDA by final state and empty stack for this given language-- L ={a^n b^n, n>=1}
3. Design a TM for the following language: L ={ a^n b^n c^n | n≥1 }.
   OR
   Design Two Stack PDA for the following language:
   L = {a^n b^n c^n | n≥1}.

Section : D ( 1 x 12 = 12 Marks )

All questions are compulsory

1. Design a TM for the following language:
   (i) 1's complement for binary number {0,1}
   (ii) 2's complement for binary number {0,1}
   OR
   Design a PDA for the following language:
   (i) Number of a's is equal to number of b's in a language.
   L = {a^n b^m c^n, n,m>=1}                                       

*******************