Nalanda Open University
Annual Examination 2016
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. Define finite automata. Explain Mealy and Moore machine with an example.
2. Define regular expression. What are the rules of writing the regular
expression? Write regular expressions for the following:
A language over the alphabet of strings of odd length.
A language over the alphabet of strings which have at the end of
each string.
3. Define Grammar and explain Chomsky's classification of grammar with examples.
4. State and prove the Pumping lemma for regular expressions.
5. Consider the following productions:
S → aB/bA
A → aS/bAA/a
B → bS/aBB/b
For the string aabbbaabba, find the left most derivation and draw the Parse
tree for the same.
6. Determine the Closure property of CFLs under the following set operations:
Union
Kleene star
Complementation
7. Build a Push Down Automata that accepts the language of odd
palindrome over the alphabet 1}. Give the computation sequence for the
input 0110110 accepted by a PDA.
8. Find the equivalent finite automata for the following regular expressions:
(ab ba)

010*10*1

9. Construct a Turing machine to accept the product function given by:
if m=0 or n=0,Else mxn}
10. State any three undecidable problems. Prove that L {anbmanbm ⌉ m
is not context free.