TOC Model Question Solution Bsc csit

TOC Model Question Solution Bsc csit

Theory Of Computation

Bsc csit 

1. Define the extended transition function of DFA. Draw a DFA accepting language L= {1n | n=2,3,4…….}. Show acceptance of strings 1110011 and 1110 using extended transition function. [2+4+4]

2. What is deterministic pushdown automaton? Configure a pushdown automaton accepting the language, L= {wCwR | w € (a,b)*}. Show instantaneous description of strings abbCbba and baCba. [2+4+4]

3. How a Turing Machine works? Construct a Turing Machine accepting the language, L= { (n )n }. Also show the transition diagram of the machine. Illustrate whether a string (( )) is accepted by the Turing Machine or not. [2+6+2]

Section B

Short Answer Questions

Attempt any Eight questions. [8*5=40]

4. When a grammar is said to be in CNF? Convert following grammar to CNF; [ 1+4]

S→ 1A | 0B | є

A→ 1AA | 0S | 0

B→ 0BB | 1 |A

C→CA | CS

5. Define epsilon NFA. Configure equivalent epsilon NFA for the regular expression

(ab U a)*. [1+4]

6. Differentiate Kleen Closure from Positive Closure. For Σ ={0,1}, compute Σ* and Σ2. [3+2]

7. Write the regular expression over {0, 1} for strings [2.5+2.5]

a. not ending with 0.

b. of length at least 3 that ends with 00.

8. What is undecidable problem? Define Post’s Correspondence Problem with an example. [1+4]

9. How pumping lemma can be used to prove that any language is not a regular language? Show that language, L={0r 1r|n ≥0} is not a regular language. [4+1]

10. Discuss how Turing Machine with multiple tracks differs from a Turing Machine with multiple tapes. [5]

11. How context free grammars are defined? Write a context free grammar over {0,1}, where the strings start and end with the same symbol. [2+3]

12. What is halting problem? How can you argue that halting problem is undecidable? [1+4]

DOWNLOAD SOLUTION⏬