0

The string $a^{i}b^{j}c^{k}$ could be generated by the following grammar:

$$ S \rightarrow SSS \space | \space aS \space | \space bS \space | \space cS \space | \space a \space | \space b \space | \space c $$

by the below derivation:

$$ S \rightarrow {\bf aS }SS \space \space \space \space (i - 1) \space times\\ S \rightarrow a^{i - 1}{\bf a}SS\\ S \rightarrow a^{i}{\bf bS }S \space \space \space \space (j - 1) \space times\\ S \rightarrow a^{i}b^{j-1}{\bf b}S\\ S \rightarrow a^{i}b^{j}{\bf cS} \space \space \space \space (k - 1) \space times\\ S \rightarrow a^{i}b^{j}c^{k-1}{\bf c}\\ S \rightarrow a^{i}b^{j}c^{k}\\ $$

However, using the pumping lemma, this has been proved to be non-CFL. Why wouldn't the above derivation work? What have I misunderstood here?

Masked Man
  • 233
  • Is there some way to place those comments (i-1) times, etc. more separated from the "equations"? I couldn't figure out any way to do this here. – Masked Man Jan 19 '14 at 08:49

1 Answers1

1

Note that $a\equiv a^{1}b^{0}c^{0}$ is not in the grammar. However, according to your derivation, it is. Your derivation and the grammar do not agree.

parsiad
  • 25,154
  • Uhm, couldn't we just add an $ S \rightarrow \epsilon $ rule? Sorry for this basic question, I am new to this and basically self-learning without any expert guidance. – Masked Man Jan 19 '14 at 09:33
  • But that would still accept $a$, which is clearly not in the grammar (i.e. it is not in the form $a^ib^jc^k$ with $i\leq j\leq k$). – parsiad Jan 19 '14 at 09:37
  • Oh, I got it now. Thanks. – Masked Man Jan 19 '14 at 10:23