TOC

Question

Explain Whether the following statements are valid or not ?

1. Grammar obtained from DFA is always unambiguous .
2. Grammar obtained from NFA is  always ambiguous .
3. Grammar obtained from DPDA is always unambiguous .

Answer 1

1) False .DFA generates regular grammar. Regular grammar can be right linear or left linear but not both . So, it can be ambiguous

S-> aS / a / ∊

here we can generate 'a' in 2 ways, So, 2 different parse tree can generate 'a'

2) As DFA accepts ambiguous grammar, NFA also accepts ambiguity. As DFA has more restriction than NFA

3) No DPDA could be generated by 2 different parse trees

S ->aSb | ab | ∊