Theory of Computation
This course presents a study of Finite State Machines and their languages. It covers the details of finite state automata, regular expressions, context free grammars. More, the course includes design of the Push-down automata and Turing Machines. The course also includes basics of undecidability and intractability.
Tribhuvan University
Institute of Science and Technology
2078
Bachelor Level / fourth-semester / Science
Computer Science and Information Technology( CSC262 )
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)
Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.
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 |
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
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.
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 3rd symbol is ‘a’ and 5th symbol is ‘b’.
Show that L = { an | n is a prime number } is not a regular language.
Explain about the Chomsky’s Hierarchy about the language and programs.
Define a Push Down Automata. Construct a PDA that accepts L = {anbn | n > 0}
Construct the following grammer into Chomsky Normal Form.
S → abSb | a | aAb
A → bS | aAAb | ε
Define Turing Machine and explain its different variations.
Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.
Explain the term Intractability. Is SAT problem is intractable? Justify