STUPIDSID
1(a)
Define the following with proper examples :
i) Alphabet ii) Powers of an alphabet.
i) Alphabet ii) Powers of an alphabet.
3 M
1(b)
Design the DFA's for the following languages:
i) Set of all strings with at least one 'a' and exactly two 'b' on\[\sum =\left \{ a,b \right \}.\]
ii) Set of all strings such that number of '1's is even and the number of '0's is a multiple of 3 on\[\sum =\left \{ a,b \right \}.\]
i) Set of all strings with at least one 'a' and exactly two 'b' on\[\sum =\left \{ a,b \right \}.\]
ii) Set of all strings such that number of '1's is even and the number of '0's is a multiple of 3 on\[\sum =\left \{ a,b \right \}.\]
8 M
1(c)
Design an NFA with no more than 5 states for the following language:
\[L=\left \{ abab^{n}|n\geq 0\right \}U\left \{ aba^{n} |n\geq 0\right \}\]
\[L=\left \{ abab^{n}|n\geq 0\right \}U\left \{ aba^{n} |n\geq 0\right \}\]
8 M
1(d)
Prove that if \[If D= (Q{D}), \sum,\delta _{D},\left \{ Q0 \right \},f_{D})\] is the DFA constructed form NFA \[N= \left ( Q_{N}\sum ,\delta _{N}Q_{0}F_{N} \right )\] by the subset construction,then L(D)=L(N).
6 M
2(a)
Convert the following \[\epsilon \] - NFA into an equivalent DFA:
| δ | ∈ | a | b | c |
| →p | {q,r} | Φ | {q} | {r} |
| *q | Φ | {p} | {r} | {p,q} |
| r | Φ | Φ | Φ | Φ |
5 M
2(b)
Define regular expression and also write the regular expressions for the following languages:
i) L=\[\epsilon \]{a,b}*| w has exactly one pair of consecutive a's}.
ii) Set of all strings not ending in substring 'ab' over \[\sum =\left \{ a,b \right \}\]
i) L=\[\epsilon \]{a,b}*| w has exactly one pair of consecutive a's}.
ii) Set of all strings not ending in substring 'ab' over \[\sum =\left \{ a,b \right \}\]
6 M
2(c)
Prove that if L= L(A) for some DFA A, then there is a regular expression R such that L=L(R).
6 M
2(d)
Obtain the regular expression for the following DFA using state elimination technique :
6 M
3(a)
State and prove pumping lemma for regular languages.
7 M
3(b)
Let \[\sum \]-{a,b},Show that the language L=\[\left \{ W\epsilon \sum \ ^*|n_{a}(w)< n_{b}(w)\right \}\] is not regular.
5 M
3(c)
Consider the DFA given by the transition table:
i) Draw the table of distinguish-abilities for this automaton.
ii) Construct the minimum state equivalent DFA.
iii) Write the language accepted by the DFA.
| δ | a | b | |
| →q0 | q1 | q2 | |
| q1 | q1 |
|
|
| q2 | q1 | q3 | |
| q3 | q1 | q4 | |
| *q4 | q1 |
|
i) Draw the table of distinguish-abilities for this automaton.
ii) Construct the minimum state equivalent DFA.
iii) Write the language accepted by the DFA.
8 M
4(a)
Define a Context-free Grammar (CFG) and also obtain the CFG's for the following languages:
i)\[L_{1}= \left \{ a^{n}WW^{R1} B^{n}|w\epsilon \left \{ 0,1 \right \}^{*}\right \} \ and \ n \geq 2 }\
ii)\[L_{2}=\left \{ a^{k}b^{m}c^{n}|m+n=k and m,n\geq 1 \right \}\]
iii) \[L_{3}=\left \{ w \ \epsilon\ \right\left \{ a \right \}^{*}|w|mod 3\ \neq |\ mod2 \}.\]
i)\[L_{1}= \left \{ a^{n}WW^{R1} B^{n}|w\epsilon \left \{ 0,1 \right \}^{*}\right \} \ and \ n \geq 2 }\
ii)\[L_{2}=\left \{ a^{k}b^{m}c^{n}|m+n=k and m,n\geq 1 \right \}\]
iii) \[L_{3}=\left \{ w \ \epsilon\ \right\left \{ a \right \}^{*}|w|mod 3\ \neq |\ mod2 \}.\]
10 M
4(b)
Consider the CFG with production
\[E\rightarrow E*\ T|T\]
\[ T\rightarrow F\ \ T \ | \ F \]
\[ F\rightarrow (E) \ |0|\ 1\] Write the leftmost derivation,rightmost derivation and parse tree for the string '0-((1*0)-0)'.
\[E\rightarrow E*\ T|T\]
\[ T\rightarrow F\ \ T \ | \ F \]
\[ F\rightarrow (E) \ |0|\ 1\] Write the leftmost derivation,rightmost derivation and parse tree for the string '0-((1*0)-0)'.
6 M
4(c)
Show that the following grammar is ambiguous:
\[s\rightarrow sbs\]
\[s\rightarrow a.\]
\[s\rightarrow sbs\]
\[s\rightarrow a.\]
4 M
5(a)
Design a PDA for the following language : \[L=\left \{ ww^{R}|w\ \epsilon \left \{ a,b \right \} +\right \}.\] Also,Draw the transition diagram for the constructed PDA. Write the instantaneous description (ID) for the string 'abbbba'.
8 M
5(b)
Convert the following CFG to a PDA that accepts the same language by empty stack:
\[E\rightarrow E+E|E*E|(E)|I)\]
\[I\rightarrow I_{a}|I_{b}I0|I1|a|b\]
\[E\rightarrow E+E|E*E|(E)|I)\]
\[I\rightarrow I_{a}|I_{b}I0|I1|a|b\]
5 M
5(c)
Define a deterministic PDA (DPDA).Also,design a DPDA Also,design a DPDA along with transition diagram for the following language:\[L=\left \{ a^{n}b^{2n} |n\geq 0\right \}.\]
7 M
6(a)
Begin with the grammar
\[S\rightarrow aAa|bBb|\epsilon \\ A\rightarrow c|a\\ B\rightarrow c|b\\ B\rightarrow CDE|\epsilon \\ D\rightarrow A|B|ab\]
i) Eliminate \[\epsilon \]- productions.
ii) Eliminate any unit productions in the resulting grammar.
iii) Eliminate any useless symbols in the resulting grammar.
\[S\rightarrow aAa|bBb|\epsilon \\ A\rightarrow c|a\\ B\rightarrow c|b\\ B\rightarrow CDE|\epsilon \\ D\rightarrow A|B|ab\]
i) Eliminate \[\epsilon \]- productions.
ii) Eliminate any unit productions in the resulting grammar.
iii) Eliminate any useless symbols in the resulting grammar.
8 M
6(b)
define Chomsky Normal From (CNF),Also,convert the following CFG to CNF:
\[ S\rightarrow AB|a \\ A\rightarrow aab\\ B\rightarrow Ac.\]
\[ S\rightarrow AB|a \\ A\rightarrow aab\\ B\rightarrow Ac.\]
6 M
6(c)
Show that the language\[L-\left \{ X\epsilon \left \{ 0,1 \right \}^{*} |\ |X|Is a perfect square\right \}is not context free.
6 M
7(a)
Define a Turing machine. Also,design a Turing machine to accept the set of all palindromes over {0,1}*.Write the transition diagram form the constructed Turing machine and write the sequence of ID's for the input string '1001'.
12 M
7(b)
Explain multitape Turing machine and non-deterministic with neat block diagrams.
8 M
8(a)
Write short notes on the following topics:
a. Applications of finite automate in text search.
b. Inherent ambiguity of context-free languages.
c. Post's correspondence problem.
d. Recursive language and it's relationship with RE and non- RE languages.
a. Applications of finite automate in text search.
b. Inherent ambiguity of context-free languages.
c. Post's correspondence problem.
d. Recursive language and it's relationship with RE and non- RE languages.
20 M
More question papers from Formal Languages and Automata Theory