Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 4 · TU Board 2078
Course Title: Theory of Computation (CSC262)
Full Marks: 60Pass Marks: 24Time: 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.
Attempt any two Questions (2 x 10 = 20)(2 × 10 = 20)
- 1.10
Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.
- 2.10
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.10
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.
- 4.10
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.
- 5.10
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'.
Answer comingAlso asked in 2076
- 6.10
Show that L = { a^n | n is a prime number } is not a regular language.
Answer comingAlso asked in 2076
- 7.10
Explain about the Chomsky's Hierarchy about the language and programs.
- 8.10
Define a Push Down Automata. Construct a PDA that accepts L = {a^nb^n | n > 0}
- 9.10
Construct the following grammer into Chomsky Normal Form.
S → abSb | a | aAb
A → bS | aAAb | ε
- 10.10
Define Turing Machine and explain its different variations.
Answer comingAlso asked in 2079
- 11.10
Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.
- 12.10
Explain the term Intractability. Is SAT problem is intractable? Justify
Attempt any Eight Questions(8 × 5 = 40)
- 1.10
Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.
- 2.10
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.10
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.
- 4.10
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.
- 5.10
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'.
Answer comingAlso asked in 2076
- 6.10
Show that L = { a^n | n is a prime number } is not a regular language.
Answer comingAlso asked in 2076
- 7.10
Explain about the Chomsky's Hierarchy about the language and programs.
- 8.10
Define a Push Down Automata. Construct a PDA that accepts L = {a^nb^n | n > 0}
- 9.10
Construct the following grammer into Chomsky Normal Form.
S → abSb | a | aAb
A → bS | aAAb | ε
- 10.10
Define Turing Machine and explain its different variations.
Answer comingAlso asked in 2079
- 11.10
Whar do you mean by computational Complexity? Explian about the time and space complexity of a Turing machine.
- 12.10
Explain the term Intractability. Is SAT problem is intractable? Justify
— The End —