0

Question from Sipser, exercise 2.29.

Prove that the language $A = \{a^ib^jc^k | i = j \text{ or } j = k \}$ is inherently ambiguous, that is, every grammar which generates $A$ is ambiguous.

So the problem here appears to be the case when $i = j = k$. The language should be able to generate strings of the form $a^ib^jc^j$, where the number of $a$'s during the generation is "independent" in some sense of the number of $b$'s and $c$'s. A similar phenomenon "should" occur with strings of the form $a^ib^ic^j$. Then, if you are dealing with a string of the form $a^ib^ic^i$, it "shouldn't be able" to tell if it came from the first algorithm where $a's$ are immaterial or the second algorithm where $c$'s are immaterial.

However, given the number of scare quotes I've placed in the above paragraph, it's probably clear that I'm out to lunch on how to prove this.

Duncan Ramage
  • 6,928
  • 1
  • 20
  • 38
  • Precise definition of 'ambiguous'? – herb steinberg Mar 19 '22 at 22:20
  • @herbsteinberg A grammar is said to be ambiguous if there exists a string in $L(G)$ which has two different left-first derivations. E.G. the grammar S -> aS | Sb | e is ambiguous because you can derive the string "ab" as S -> aS -> aSb -> ab or S -> Sb -> aSb -> ab. – Duncan Ramage Mar 19 '22 at 22:22
  • Yuval Filmus gave an answer to your question in this answer to another question. – J.-E. Pin Mar 19 '22 at 23:00
  • @J.-E.Pin Thank you. Unfortunately I don't see why it's clear that those strings would have different derivations. I would appreciate anyone who could expound on it. – Duncan Ramage Mar 20 '22 at 01:23

0 Answers0