STUPIDSID
1 (a)
What is Automata? Discuss why study automata.
6 M
1 (b)
Mention the difference between DFA, NFA and NFA → ∈.
4 M
1 (c)
Design a DFA to accept the language L=(W/W is of even length and begins with 01).
6 M
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}
i) abc, abd and aacd {Assume ∑=a, b, c, d}
ii) {ab, abc}* {Assume ∑=a, b, c}
4 M
2 (a)
Convert the following NFA→∈ to DFA using ?Subset construction scheme?
8 M
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.
i) L={a2nb2m: n≥0, m≥0}
ii) Language over {0, 1} having all strings not containing 00.
6 M
2 (c)
Convert the regular expression (0+1)*1(0+1) to a NFA→∈.
6 M
3 (a)
State and prove pumping Lemma theorem for regular language. Show that L={an bn| n≥0} is not regular.
8 M
3 (b)
What is Homomorphism? Explain with an example.
4 M
3 (c)
Consider the transition table of DFA given below:
i) Draw the table of distinguishabilities of states.
ii) Construct the equivalent minimized DFA.
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 M
4 (a)
Obtain a grammar to generate integers and write derivation for the unsigned integer 1965.
8 M
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.
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 M
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 M
5 (b)
Convert the following CFG to PDA:
S→aABB|aAA
A → aBB|a
B→ bBB|A
C→ a
S→aABB|aAA
A → aBB|a
B→ bBB|A
C→ a
8 M
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.
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 M
6 (b)
Show that L={an bn cn | n≥0} is not context free.
4 M
6 (c)
Prove that the context free languages are closed under union, concatenation and reversal.
8 M
7 (a)
Design a turbine machine that performs the following function:
q0ω|- *qf ωω for any ω ∈{1}* and also write its transition diagram.
q0ω|- *qf ωω for any ω ∈{1}* and also write its transition diagram.
12 M
7 (b)
Explain the general structure of multitape and non deterministic Turing machines.
8 M
Write short notes on:
8 (a)
Applications of regular expressions.
5 M
8 (b)
Applications of context free Grammars.
5 M
8 (c)
Post's correspondence problem.
5 M
8 (d)
Chomsky hierarchy.
5 M
More question papers from Formal Languages and Automata Theory