0

I have recently starting studying Theory of computation. I have some basic doubts. Can you please clarify my doubts?

Inherently ambiguous CFL means there is no unambiguous grammer(why can'nt we say atleast 1 possible grammer for that CFL are ambiguous?). Also can you please explain difference between ambiguous CFL and ambiguous grammer

Another doubt -

I saw that set of palindromes is inherently unambiguous. It means all grammers possible for that language of palindromes is unambiguous. But i saw in textbook example that $S \to aSa/bSb/ \epsilon $ is ambiguous(Please correct me if i am wrong here). Then how can the set of palindromes inherently unambiguous.

Nascimento de Cos
  • 793
  • sir please check now. correct me if i am going wrong – Nascimento de Cos Aug 29 '19 at 18:52
  • 1
    The language generated by the grammar you cite seems to be all palindromes of even length over ${a,b}$. It doesn't generate the palindrome "a" for example. Also it isn't ambiguous. At all stages, we have $k$ terminals, followed by $S$, followed by the initial $k$ terminals in reverse. If the string is longer than $2k$, there is no question of which production to use: it must be the one corresponding to character $k+1$ of the target string. – saulspatz Aug 29 '19 at 18:58
  • 1
    At "least one ambiguous grammar" doesn't work. Suppose I have a CFL L produced by an unambiguous grammar, and that "foo" is a word in the language. Then I add the production $S\to$ "foo" and I have an ambiguous grammar for L. – saulspatz Aug 29 '19 at 19:01
  • Sir even odd length palindromes also not ambiguous right(appending the above productions with a and b terminals). In 2nd statement, can you pls elaborate? the words are bit confusing for me. I understood that you made unambiguous grammer which can be converted to ambiguous grammer. You mean to say that if there is no unambiguous grammer(directly) AND IF THERE IS SOME AMBIGUOUS GRAMMER IT MUST NOT BE CONVERTIBLE TO UNAMBIGUOUS GRAMMER? – Nascimento de Cos Aug 29 '19 at 19:17
  • SIR also i saw in textbook that ambiguous grammer can be converted into unambiguous grammer. Can ANY ambiguous grammer be converted to unambiguous grammer? What can we say about unambiguous grammer to ambiguous grammer(I know this is useless. We generally do other direction. But wanted to know can unambiguous grammer has with any modification ambiguous grammer version?) – Nascimento de Cos Aug 29 '19 at 19:20
  • 1
    I just gave you an example of converting an unambiguous grammar (Note the spelling of "grammar") to an unambiguous one, in answer to your question of why a single ambiguous grammar is not enough to classify a language as inherently ambiguous. No, it is not the case that any ambiguous grammar can be converted to an unambiguous one. If that were true, there would be no inherently ambiguous CFL, correct? – saulspatz Aug 29 '19 at 19:24
  • got it sir, thank you for the detailed explanation. – Nascimento de Cos Aug 29 '19 at 19:27

0 Answers0