TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2081 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.
- 1Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA. $S \rightarrow AS \mid \epsilon$ $B \rightarrow aAb \mid Bb \mid ab$
- 2List any two regular operators. Minimize the following finite state machine using Table Filling algorithm. [Finite state machine diagram/image to be added manually]

- 3Define Turing machine as enumerators of strings of a language. Encode the Turing machine $TM = (\{q_0, q_1, q_2\}, \{a, b\}, \{a, b, B\}, \delta, q_0, B, F)$, with input $w = ba$ and $\delta$ is defined as follows. $\delta(q_0, b) = (q_2, a, R)$, $\delta(q_2, a) = (q_1, b, R)$, $\delta(q_2, b) = (q_1, a, R)$, $\delta(q_2, B) = (q_2, b, L)$
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Does machine always refer to hardware? Justify. Define positive closure and kleene closure.
- 5What is undecidable problem? Discuss about Post's Correspondence Problem.
- 6Define the language of a grammar. For the grammar $S \rightarrow 0S0 \mid 0 \mid 1 \mid \epsilon$, show the leftmost derivation for the string $00100$ with its parse tree.
- 7Define $\epsilon$-closure of a state. Differentiate between Moore and Mealy machine.
- 8Represent the following regular grammar to finite automata. $S \rightarrow a \mid aA \mid bB \mid \epsilon$ $A \rightarrow aA \mid aS$ $B \rightarrow bS \mid \epsilon$
- 9Design the DFA that accepts binary string ending with "$00$" and show its extended transition function for the string $111000$.
- 10Convert the following grammar to CNF. $S \rightarrow AAB$, $A \rightarrow aAb \mid \epsilon$, $B \rightarrow aB \mid a$
- 11For the following Turing Machine, test whether the string "$())($" is accepted or rejected and represent it in transition diagram.

- 12Differentiate between Class $P$ and Class $NP$ problem. Mention the transition function of DFA, NFA and $\epsilon$-NFA.