Osmania University (OU) 2007-2nd Sem B.E Information Technology 3ryr -e Theory Of Automata - Question Paper
B.E. 3/4 (IT ) II Semester (Main) Examination, April/May 2007
Subject: Theory of Automata (Elective-I)
Time : 3 Hours Max. Marks: 75
Note: Answer all questions of Part - A and
answer any FIVE questions from Part - B.
PART-A (25 Marks)
1. Define Grammar. Mention types of Grammars. 3
2. What is the difference between DFA & NFA. 2
3. Define mealy machine. 2
4. Define right most derivation of a sentence. Explain with an example. 3
5. What are useless productions in the following grammar. 4
S -> a S/A/C A -> a B-)aa C -> a C b
6. What is the speciality of PDA. 3
7. Mention the types of tying machines. 2
8. Define LR (K) grammar. 2
9. Mention ID-format for TM. 2
10. Give a grammar, which can generate palindromes. 2
PART-B (50 Marks)
11 .a. Design DFA which accepts sentences having | | As a substring; 5
alphabet is (0,1) justify design with example.
b. Design DFA which accepts sentences having Odd no. of as
alphabet = (a.b) justify design with example. 5
12. Mention algorithm for minimization of FSM. Explain with the help
of an example. 10
13. Design CFG for language a'b'/ i S: 0. 10
14. Explain the methodology for simplification of a CFG. Explain with
an example. 10
15. Convert the following grammar to GNF. 10
G = ({A1,A2fA3}I{alb},PlA1)
P : - Ai A2 A3 | A3 a
A2 A3 A1 j A3 A1 A2
A2 b |
16. Design PDA to accept an b2n ; nl justify design with example. 10
|
Attachment: |
| Earning: Approval pending. |
