written 6.7 years ago by |
Formal Languages and Automata Theory - Dec 2015
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) What is Automata? Discuss why study automata.(6 marks)
1 (b) Mention the difference between DFA, NFA and NFA → ∈.(4 marks)
1 (c) Design a DFA to accept the language L=(W/W is of even length and begins with 01).(6 marks)
1 (d) Design the NFA→∈ or NFA for the language given below:
i) abc, abd and aacd {Assume ∑=a, b, c, d}
ii) {ab, abc}* {Assume ∑=a, b, c}(4 marks)
2 (a) Convert the following NFA→∈ to DFA using ?Subset construction scheme?
(8 marks)
2 (b) Define Regular expression and write regular expression for the following languages:
i) L={a2nb2m: n≥0, m≥0}
ii) Language over {0, 1} having all strings not containing 00.(6 marks)
2 (c) Convert the regular expression (0+1)*1(0+1) to a NFA→∈.(6 marks)
3 (a) State and prove pumping Lemma theorem for regular language. Show that L={an bn| n≥0} is not regular.(8 marks)
3 (b) What is Homomorphism? Explain with an example.(4 marks)
3 (c) Consider the transition table of DFA given below:
i) Draw the table of distinguishabilities of states.
ii) Construct the equivalent minimized DFA.
0 | 1 | |
→A | B | A |
B | A | C |
C | D | B |
*D | D | A |
E | D | F |
F | G | E |
G | F | G |
H | G | D |
(8 marks)
4 (a) Obtain a grammar to generate integers and write derivation for the unsigned integer 1965.(8 marks)
4 (b) Consider the grammar:
S→aS|aSbS|∈
Is the above grammar ambiguous? Show that the string aab has two-
i) Parse trees
ii) Left most derivations
iii) Rightmost derivations.(12 marks)
5 (a) Define PDA. Design PDA to accept the language L(M)={ωCωR|ω∈(a+b)} by a final state and also give the graphical representation of PDA.(12 marks)
5 (b) Convert the following CFG to PDA:
S→aABB|aAA
A → aBB|a
B→ bBB|A
C→ a(8 marks)
6 (a) Consider the following grammar:
S→ ASB|∈
A→ aAS|a
B→ SbS|A|bb
i) Are there any useless symbols? Eliminate if so.
ii) Eliminate ∈ productions.
iii) Eliminate unit productions.
iv) Put the grammar into Chomsky Normal Form.(8 marks)
6 (b) Show that L={an bn cn | n≥0} is not context free.(4 marks)
6 (c) Prove that the context free languages are closed under union, concatenation and reversal.(8 marks)
7 (a) Design a turbine machine that performs the following function:
q0ω|- *qf ωω for any ω ∈{1} and also write its transition diagram.(12 marks)
7 (b) Explain the general structure of multitape and non deterministic Turing machines.(8 marks)
Write short notes on:
8 (a) Applications of regular expressions.(5 marks) 8 (b) Applications of context free Grammars.(5 marks) 8 (c) Post's correspondence problem.(5 marks) 8 (d) Chomsky hierarchy.(5 marks)