How is $L = \{ a^{i}b^{j}c^{k} \space | \space 0 \le i \le j \le k \}$ not a CFL?

57 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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.