retagged by
2,376 views

2 Answers

1 votes
1 votes

Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable. Here are the original references:

Since S-Grammer is also a CFG the ambiguity is undecidable

it is decidable whether a regular grammar is ambiguous (the inherent ambiguity problem is not very challenging on regular grammars, since the answer is invariably "no" without even looking at the input grammar). This can be checked in O(|G|2) using a squaring construction on its associated automaton: construct the product of the automaton with itself, and see whether some state (q,q′)(q,q′) with q≠q′q≠q′ is accessible and co-accessible. The oldest reference I know for this idea is a paper by Even (1965).

0 votes
0 votes
1.the s grammar are of type V->TV* & for every <V,T> pair we have a unique production. clearly, this property of s grammar make it unambiguous.

2. for every regular set their exists at least one unambiguous regular grammar.

Related questions

0 votes
0 votes
0 answers
2