STUPIDSID
1(a)
Define the following with examples: i) Alphabet, ii) String.
4 M
1(b)
Define DFA. Write the DFA's for the following languages on ∑={a,b}.
i) The set all strings containing the substring 'ab'.
ii) L = {ω |ω| mod 3=0}
i) The set all strings containing the substring 'ab'.
ii) L = {ω |ω| mod 3=0}
8 M
1(c)
Convert the following NFA to its equivalent DFA.
8 M
2(a)
Define a regular expression. Also write the regular expressions for the following languages.
i) The set of all strings ending in the substring '00' on ∑={0,1}
ii) L = {anbm | n≥4, m≤3}.
i) The set of all strings ending in the substring '00' on ∑={0,1}
ii) L = {anbm | n≥4, m≤3}.
8 M
2(b)
Prove that every language defined by a regular expression is also defined by a finite automation.
8 M
2(c)
Write the ∈-NFA for the regular expression ab(a+b)*.
4 M
3(a)
State and prove pumping lemma for regular languages.
7 M
3(b)
Show that the language L = {anbn | n≥0} is not regular.
6 M
3(c)
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 |
7 M
4(a)
Define CFG. Design CFG's for the following languages:
i) L = {anb2n | n≥0}
ii) L = {ω;ωR / ω∈ {a,b}*}
i) L = {anb2n | n≥0}
ii) L = {ω;ωR / ω∈ {a,b}*}
8 M
4(b)
Write the LMD, RMD and parse tree for the string '+*-xyxy' using the grammar
E → EE | *EE | -EE | x | y
E → EE | *EE | -EE | x | y
6 M
4(c)
What is an ambiguous grammar? Show that the following grammar is ambiguous:
E → E + E | E * E | (E) | id
E → E + E | E * E | (E) | id
6 M
5(a)
Define a PDA and explain the working of it with a neat diagram.
5 M
5(b)
Design a PDA for the language L = {ωωR | ω ∈ {a, b}'. Draw the transition diagram and also write the sequence od ID's for the string 'abba'.
10 M
5(c)
Convert the following CFG to an equivalent PDA:
S → aA
A → aABC|bB|a
B → b
C → c
S → aA
A → aABC|bB|a
B → b
C → c
5 M
6(a)
Eliminate the useless symbols and productions from the following grammer.
S → AB|AC
A → aA|bAa|a
B → bbA|aB|AB
C → aCa|aD
D → aD|bC
S → AB|AC
A → aA|bAa|a
B → bbA|aB|AB
C → aCa|aD
D → aD|bC
7 M
6(b)
Define CNF and convert the following grammer into CNF.
S → Aba
A → aab
B → Ac
S → Aba
A → aab
B → Ac
6 M
6(c)
Prove that the family of context-free languages is closed under union, concentration and star-closure.
7 M
7(a)
Define a turing machine and explain the working of a basic turing machine with a neat diagram.
8 M
7(b)
Design a turing machine for the language L = {anbn | n≥1}. Write the transition diagram for the same and also, indicate the moves by the machine for the input 'aabb'.
12 M
Write short notes on
8(a)
Multitape turing machine
5 M
8(b)
post's correspondence problem
5 M
8(c)
Applications of context-free languages.
5 M
8(d)
Chomsky hierarchy
5 M
More question papers from Formal Languages and Automata Theory