Bachelor in Computer Application Part-III
Paper-XX [Theory of Computer Science
Time: 3.00 Hrs. Full Marks: 80
Answer any Five questions. All questions carry equal marks.
1. What is Regular grammar? Explain the rules of writing the regular grammar and give
examples of each.
2. State the pumping lemma of regular grammar. Show that {an bn is not regular.
3. What is NULL-NFA? Using an example convert a NULL-NFA to DFA.
4. Build a Push Down Automata that excepts the language over the alphabet where
each word is an even palindrome in a and b.
5. Determine the Closure property of Context Free Languages under the following set
operations:
Union
Kleene star
Complementation
Concatenation
6. Define Type-2 grammar. Find the highest type that can be applied to the following
productions:
S → Aa, A→c|Ba, B→abc
S→ASb|d A → aA
Explain any three uses of regular expressions.
7. Find the equivalent finite automata for the following regular expressions:
(101 11.
ba bb*ab)
(ab ba aa)

8. Construct a Turing machine to accept the product function given by:
if m=0 or Else
9. What is primitive recursion? Explain that product function is primitive recursive. Give proper
examples to explain the concept.
10. Write short notes on any three:
Mealy machine.
Moore machine
(iii)Ambiguity
(iv)Equivalence of DFA and NFA.