2. Show that the CFG with the following productions is ambiguous.
S
a Sa bSS SSb SbS
→ | |
|
|
|
3. When NFA becomes DFA?
4. List the properties of Finite State Machine.
5. Define tree automata.
6. What is priority rewriting?
7. Define Kleene closure.
8. What is star free sets?
9. State the two methods used by PDA to accept a language.
10. Define Rabin tree automation.
PART B
11. Construct DFA accepting each of the following languages.
(a) W a b
∈{ , }
* each a in W is immediately proceded and immediately
followed by “ab”.
(b) W a b W
∈{ , } :
*
has “abab” as a substring.
12. Construct and explain special automata for the given string “abbaab”.
13. Design a Push Down Automata to accept the strings of the grammar.
G E
r E r e E e e
:
|
| .
→
Explain the sequence of moves.
14. Find star heights of the following regular expressions.
(a) ( (
) )
*
* *
a ab c
(b) ( (
) )
* * *
c a b
(c) (
)
*
*
*
a
b
ab
∪ ∪
(d) (
)
*
*
abb a
15. Write markov algorithm to find the following.
(a) Reverse of the given string “abcd”
(b) Whether a given decimal number is divisible by 3.
16. Construct NFA accepting the following languages over alphabet {0, 1}
(a) The set of all strings with 3 consecutive 0’s (zeroes).
(b) The set of all strings such that every block of five consecutive symbols contains atleast 2 zeroes.
(c) The set of all strings ending in oo.
END
322
Theory of Automata, Formal Languages and Computation