Bachelors Level/Second Year/Fourth Semester/Science csit/fourth semester/theory of computation/syllabus wise questions
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Theory of Computation (CSC262)
Year Asked: 2078, syllabus wise question
Basic Foundations
1.
Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.[5]
2.
Explain about the Chomsky's Hierarchy about the language and programs.[5]
Context Free Grammar
1.
Construct the following grammar into Chomsky Normal Form.
S→abSb∣a∣aAb
A→bS∣aAAb∣ε
[5]
Introduction to Finite Automata
1.
Give the formal definition of DFA and NFA. How NFA can be converted into equivalent DFA? Explain with suitable example.[10]
2.
Find the minimum state DFA for the given DFA below:
StatesABC∗DEF0BEBEBB1FCDFCA
[10]
Push Down Automata
1.
Define a Push Down Automata. Construct a PDA that accepts L = {anbn∣n>0}.[5]
Regular Expressions
1.
Give the regular expressions for the following language over alphabet {a, b}. a. Set of all strings with substring bab or abb. b. Set of all strings whose 3rd symbol is 'a' and 5th symbol is 'b'.[5]
2.
Show that L = {an | n is a prime number} is not a regular language.[5]
Turing Machines
1.
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.[10]
2.
Define Turing Machine and explain its different variations.[5]
3.
What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine.[5]
Undecidability and Intractability
1.
Explain the term Intractability. Is SAT problem is intractable? Justify[5]