Peter Linz 5.1

Question

I need two proves, i am stuckhere

1.Show that every S-grammar is Unambiguous

2.Show that a RegEx can never be Inherently Ambiguous

so what to use here? Induction/Contradiction

Answer 1

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:

• The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and Schützenberger (1963). The proofs in textbooks typically reduce from the Post Correspondence Problem.
• The undecidability of inherent ambiguity was proved by Ginsburg and Ullian (1966).

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).

Comments

When we say a set has a property in the sense that it's members obeys that then every subset of it also has it. For example, CFLs are acceptable by PDA. But when we say a property in terms of a set (not elements) like CFLs are closed under union, it may or may not be followed by its subsets. (DCFLs are not closed under union).

Now for the given question the argument given for S-grammar is not a valid proof. It is a CFG but that does not make its ambiguity problem undecidable. We have to explicitly prove this case for S-grammar or show that it is always unambiguous. The place to start the proof would be the properties of S-grammar.

---

Sir i think when we talk about ambiguity for CFG and say its undecidable we basically declare this for CFG those are not Reg grammar.

---

Would you like to explain your statements by taking any small regular grammar?That would make the analysis more clear.

Answer 2

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.