TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2080 B.S.
Candidates are required to give their answers in their own words as far as practicable.
Group A
Long Answer QuestionsAttempt any Two questions.
- 1Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram, over $\Sigma = \{0, 1\}$ that accepts the strings having substring $01$ and ends with $1$. Show the acceptance of $0111$.
- 2Define CFG. Construct a CFG that generates the language of all palindromes over $\Sigma = \{a, b\}$ that do not contain the substring $aa$. Show the leftmost derivation and construct the equivalent parse tree for string $babbbab$.
- 3How Turing Machine is used as a computing function? Construct a TM for simulating a function $f(x) = 2x$ for $x = \{1\}$. Iterate the TM for input $11$ and generate the output $1111$.
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Differentiate Kleen closure from Positive closure. Compute Positive and Kleen closure of $\{ab\}$.
- 5Design a Mealy machine over $\Sigma = \{a, b\}$ that generates output 'A' if the input string ends with $aa$ else output 'B' if the string ends with $bb$.
- 6Construct regular expression over $\{1, \ldots, 9\}$ that represents: a. strings of even numbers with length $4$ starting with $2$ and ending with $8$ b. strings starting with odd numbers and ending with even numbers
- 7Prove that the language $L = \{a^n b^n c^n \mid n \geq 0\}$ is not context free.
- 8Construct a PDA that accepts strings over $\Sigma = \{a, b\}$ that contains equal number of $a$'s followed by equal number of $b$'s. Show acceptance of $aabb$ and $aab$.
- 9Describe how multi-stack TM is different from the semi-infinite tape TM?
- 10What is intractability? Define time and space complexity of Turing Machine.
- 11How conversion of PDA to CFG is done? Illustrate with an example.
- 12State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.
