5:41 AM
VAAGESWARI COLLEGES
1 Define DFA and NFA. Give examples
2 Convert the following NFA to equivalent DFA:
3 Define regular expression. Give example. Write its applications
4 Design a DFA that accepts the language over ∑ = {a, b} of all strings that
contain the sub-string either aa or bb.
5 Describe Chomsky hierarchy of languages and recognizers.
6 Convert the following regular expressions into NFA. [6+10]
(i) (0 U 1)*000(0 U 1)*
(ii) (((00)*(11))U01)*
(iii) φ*
7 Describe parse trees.
8 Consider the following recursive grammar:
i. S -> Aa |b
ii. A -> Ac |Sd
What is an equivalent grammar when the left recursion is removed?
9) Identify the language, L generated by the following grammar, G:
G = ({S,A,B}, {a, b}, {S -> Aa, A -> a |B ,B -> bB | b }, S).
10) Explain about ambiguous grammar?
11) What is left factoring? Explain with a suitable example.
12) Explain Bottom up parsing with example
13) Consider the following augmented grammar:
S -> E
E -> E + T|T
T -> a |(E)
Construct the SLR(1) parse table.
14) What is syntax directed translation? Explain with example.
15) Describe about S-attributed and L-attributed grammars.
16) Compare Inherited attributes and Synthesized attributes with an example
