Computer Science Engg. (Semester 5)
TOTAL MARKS: 100
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks.
1 (a) Mention the difference between DFA,NFA and ?-NFA.(6 marks)
1 (b) Design a DFA which accept set of all string of 0's and 1's beginning with a 1 that,when interpreted as a binary integer ,is a multiple of 5.For example strings 101,1010 and 1111 are in the language :0,100,0101 and 111 are not (6 marks)
1 (c) Convert the following NFA to DFA using construction method:
| δ | 0 | 1 |
| →p | {p,q} | {p} |
| q | φ | {r} |
| r | {p,r} | {q} |
(8 marks)
2 (a) Consider the following ?-NFA:
Compuer the ?-closure of each state .
Give the set of all string of lenghth 3 or less accepted by the automation
Convert the automation to DFA. | δ | ∈ | a | b |
| → | {r} | {q} | {p,r} |
| q | φ | {p} | φ |
| *r | {p,q} | {r} | {p} |
(8 marks)
2 (b) Give the regular expression for the following languages:
L={a n b m:n ?4,m ?2};
L={w:w?(0,1) and |w| mod 3=0}(4 marks)
2 (c) mention the application of regular expression (2 marks)
2 (d) prove that every language defined by RE is also defined by some finite automataion(6 marks)
3 (a) State and prove that pumping lemma of regular languages (6 marks)
3 (b) Obatin the regular expression or distinguish ?Minimize the following DFA using table finite automation using state climatation method
(4 marks)
3 (c) When two sates are equivalent or distingushable ?minimize the following DFA using table filling algorithm
| δ | 0 | 1 |
| →q1 | q2 | q3 |
| q2 | q3 | q5 |
| q3 | q4 | q3 |
| q4 | q3 | q5 |
| *q5 | q2 | q5 |
(10 marks)
4 (a) Decline CFG .Design a context free grammer for the language :
L={a i bj ck, where i=J+k.j,k?0}
L={0 n+21n:n ?1}(8 marks)
4 (b) What is an ambigous grammer? Show that grammer shown below is ambigous
S?AB|aaB
A&rarr|a
B ?b(6 marks)
4 (c) Consider the grammer
E?+EE/EE/-EE/x/y
Find the left most derivation ,right most derivation and parsetree for the string "+ * - xyxy.(6 marks)
5 (a) Discuss the language accepted by a PDA .design to PDA to accept the following language L=0<suo>2n 1n n?1}.draw the transmistion diagram for the constructed PDA ,Also show the moves made by PDA for the string "000011"</suo>(14 marks)
5 (b) Convert the following grammer to PDA that accept the same by empty stack: S?aABB/aAA
A?aBB/a
B?bBB/a
C ?a(6 marks)
6 (a) What are useless production ? Eliminate ? unit and unless production from following grammer
A?bA/Bba/aa
B ?aba/b/D ,
C ?CA/AC/B ,
D ?a /?(10 marks)
6 (b) Define chomskey normal form .convert the following CFG to CNF
S ?aSb/ab /Aa
A ? aab (6 marks)
6 (c) prove that the context free languages are closed under union(4 marks)
7 (a) Design a turing machine to accept the languages L={ww R:w?(a,b)*}.write its transition diagram .Also show the sequence of moves made by the TM for the string "aabbaa"(14 marks)
7 (b) Define turing machin .Explain with a diagram general structure of multiple turning machine(6 marks)
Write short note on:
8 (a) Recursive language(5 marks)
8 (b) universal turing machine (5 marks)
8 (c) Post correspondance problem(5 marks)
8 (d) Application Of Context free grammer(5 marks)
and 5 others joined a min ago.
teamques10
★ 68k
sagarkolekar
★ 11k