TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2083 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.
- 1Construct a nondeterministic finite automaton (NFA) over the alphabet $\{0,1\}$ that accepts all strings containing the substring 101. Using the subset-construction method, convert the NFA into an equivalent deterministic finite automaton (DFA).
- 2Simplify the following context-free grammar by successively removing useless symbols, nullable symbols, and unit productions, and write the resulting equivalent grammar: $S \to AB \mid aA$, $A \to aA \mid \epsilon$, $B \to bB \mid C$, $C \to b$, $D \to dD$.
- 3Design a Turing machine that accepts the language $L = \{0^n1^n \mid n \geq 1\}$, and specify its components, transition notation, and the sequence of moves used to accept an input string such as 0011.
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Let $\Sigma = \{a,b\}$. Define the power of the alphabet, Kleene closure, and positive closure of $\Sigma$, and list the first five strings in $\Sigma^*$ and $\Sigma^+$.
- 5Differentiate between Moore and Mealy machines with example.
- 6Define an $\epsilon$-NFA and explain the concept of $\epsilon$-closure of a state with a suitable example.
- 7Explain the closure properties of regular languages under union, intersection, and complement operations.
- 8Using the pumping lemma for regular languages, determine whether the language $L = \{0^n1^n \mid n \geq 0\}$ is regular.
- 9Explain the types of derivations used in a context-free grammar (CFG), and show that the grammar $E \to E+E \mid E*E \mid (E) \mid id$ is ambiguous by constructing two distinct parse trees for the string $id + id * id$.
- 10Explain the two methods of accepting a language by a pushdown automaton (PDA), namely acceptance by final state and acceptance by empty stack, and state how they differ.
- 11What is meant by using a Turing machine as a subroutine, and why is this concept useful in designing complex Turing machines?
- 12What is Turing reducibility, and how can it be used to establish a relationship between the Circuit Satisfiability problem and another computational problem?