Tribhuvan University

Institute of Science and Technology

2078

Bachelor Level / fourth-semester / Science

Computer Science and Information Technology( CSC257 )

Theory of Computation

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

**Long Answer Questions**

**Attempt any two Questions (2 x 10 = 20)**

1

Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

2

Find the minimum state DFA for the given DFA below:

States | Input | |

0 | 1 | |

A | B | F |

B | E | C |

C | B | D |

*D | E | F |

E | B | C |

F | B | A |

3

Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recognized by Universal Turing Machine.

**Short Answer Questions**

**Attempt any Eight Questions**

4

Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.

5

Give the regular expressions for the following language over alphabet {a, b}.

- Set of all strings with substring bab or abb.
- Set of all strings whose 3
^{rd}symbol is ‘a’ and 5^{th}symbol is ‘b’.

6

Show that L = { a^{n} | n is a prime number } is not a regular language.

7

Explain about the Chomsky’s Hierarchy about the language and programs.

8

Define a Push Down Automata. Construct a PDA that accepts L = {a^{n}b^{n} | n > 0}

9

Construct the following grammer into Chomsky Normal Form.

S → abSb | a | aAb

A → bS | aAAb | ε

10

Define Turing Machine and explain its different variations.

11

Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.

12

Explain the term Intractability. Is SAT problem is intractable? Justify

HAMROCSIT.COM