2 votes 2 votes 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 Theory of Computation theory-of-computation context-free-language regular-expression regular-language grammar + – No_name asked Apr 7, 2017 • retagged Jul 4, 2017 by Arjun No_name 2.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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: 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). Deepthi_ts answered Apr 8, 2017 Deepthi_ts comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Arjun commented Apr 10, 2017 reply Follow Share 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. 1 votes 1 votes Rupendra Choudhary commented May 24, 2017 reply Follow Share 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. 1 votes 1 votes sandyoverflow commented Oct 20, 2018 reply Follow Share Would you like to explain your statements by taking any small regular grammar?That would make the analysis more clear. 0 votes 0 votes Please log in or register to add a comment.
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. manikantsharma answered Mar 11, 2020 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.