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 \rightarrow abSb \mid a \mid aAb$
$A \rightarrow bS \mid aAAb \mid \varepsilon$
[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:
$\begin{array}{|c|c|c|} \hline \text{States} & 0 & 1 \\ \hline A & B & F \\ B & E & C \\ C & B & D \\ *D & E & F \\ E & B & C \\ F & B & A \\ \hline \end{array}$
[10]
Push Down Automata
1.
Define a Push Down Automata. Construct a PDA that accepts L = {$a^n b^n | 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 = {$a^n$ | 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]