TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2082 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.
- 1List the applications of Pumping Lemma. Minimize the following DFA using Table Filling Algorithm.
- 2Define yield in parse tree with example. Convert the following grammar to CNF.
- 3Distinguish between multi-tape and multi-track Turing Machine. Design a TM that accepts a string over alphabet \(\Sigma = \{a, b\}\), such that \(L = \{a^n b^n \mid n > 0\}\).
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Why do we need asymptotic notation? Discuss about alphabet and power of alphabet.
- 5Define ambiguous grammar. How do you use parse tree to show the ambiguity of a grammar?
- 6Given the non-deterministic Turing machine: \(TM = (\{q_0, q_1, q_2, q_f\}, \{0, 1\}, \{0, 1, B\}, \delta, q_0, B, \{q_f\})\) with the following transition rules, describe the language accepted by the given Turing machine.
- 7Given two DFAs \(M_1\) and \(M_2\) over the same alphabet \(\Sigma\), design a third DFA \(M_3\) such that \(M_3\) will accept the string \(w \in \Sigma^*\) if it is accepted by both \(M_1\) and \(M_2\).
- 8Differentiate between Moore and Mealy machines.
- 9Design a DFA that accepts the odd length of binary strings.
- 10How do you convert CFG to PDA? Explain.
- 11Why do we need \(\epsilon\)-transition? Give the formal definition of PDA.
- 12Describe about abstract, decision and optimization problems.