642 views
2 votes
2 votes
are grammars corresponding to DFA's unambiguous and those to NFA's are ambiguous? according to what I studied every DCFL is guaranteed has an unambiguous grammar though there are multiple grammars generating them every regular language is also DCFL hence they will follow the same but I doubt if every grammar corresponding to DFA is non-ambiguous and that of NFA is ambiguous

1 Answer

1 votes
1 votes
Grammar corresponding to DFA is unambiguous because we have only transition on a terminal from the state in the DFA,

ex   $a^{*}$  it have only self loop

and the grammar corresponding to the NFA  can be ambiguous  because from the same state with a terminal we can go to one or more different state

but there will be at least one unambiguous grammar for every NFA.

Related questions

1 votes
1 votes
1 answer
1
akhileshreddy asked Jul 12, 2017
560 views
L = {a^nb^m : n >= m+3}below context grammer is correct??S == aA | AaA == aAb | bAa | abA | baA | aa
1 votes
1 votes
2 answers
3