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: 2076, syllabus wise question
Context Free Grammar
1.
Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.[5]
Introduction to Finite Automata
1.
Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0's and even number of 1's.[5]
2.
Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.[5]
Push Down Automata
1.
How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.[10]
2.
Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and 1s. Show by sequence of IDs that 0101 is accepted by this PDA.[5]
Regular Expressions
1.
Define the NFA with ϵ−transition and ϵ−closure of a state. Show that for every regular expression r, representing a language L, there is ϵ−NFA accepting the same language. Also convert regular expression (a+b)*ab* into equivalent Finite Automata.[10]
2.
Give the regular expressions for following language over alphabet {0, 1}. a. Set of all strings with 2nd symbol from right is 1. b. Set of all strings starting with 00 or 11 and ending with 10 or 01.[5]
3.
Show that language is not a regular language.
L={0m1m∣m≥1}
[5]
Turing Machines
1.
Define a Turing machine. Construct a TM that accept L={wcwR∣w∈{0,1} and c is ε or 0 or 1}. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID).[10]
2.
Describe the Turing machines with multiple tape, multiple track and storage in state.[5]
3.
Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.[5]
Undecidability and Intractability
1.
What do you mean by tractable and Intractable problems? Explain with reference to TM.[5]