TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2079 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.
- 1Show that, for any NFA accepting language $L$, there is a DFA $D = (Q, \Sigma, \delta, q_0, F)$ accepting the same language $L$.
- 2State and prove the pumping lemma for regular languages. How can you show with example the pumping lemma is used to prove that a given language is not regular?
- 3Given the following expression grammar for simple arithmetic expression with operator $+$ and $*$. [Grammar/image to be added manually]
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Explain the $\epsilon$-closure of states of an $\epsilon$-NFA with a suitable example.
- 5Convert the following regular expression into equivalent Finite Automata. a. $(0+1)^*(10(1+0)$ b. $1^*0(0+1)^*1$
- 6Define the term: Parse Tree, Left-most and right-most derivation, sentential form and ambiguity with example.
- 7Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA? Explain with an example.
- 8Define regular grammar. Also explain the method of converting right linear grammar into equivalent Finite Automata.
- 9Construct a Turing Machine that accepts a language [language definition/image to be added manually]
- 10Define Turing Machine and explain its roles.
- 11Explain about the complexity classes $P$, $NP$ and $NP\text{-}Complete$.
- 12Write short notes (Any two): a. Big $O$, Big $\Omega$ and Big $\Theta$ b. Tractable and Intractable Problems c. Chomsky Hierarchy