I'm currently working with this grammar:

  1. $S \to aSBC$
  2. $S \to aBC$
  3. $CB \to BC$
  4. $aB \to ab$
  5. $bB \to bb$
  6. $bC \to bc$
  7. $cC \to cc$

It is supposed to define the language $$ L = \{a^nb^nc^n : n \geq 1\}. $$

I need to know how to get through the grammar rules to end up with $L$. So I started with the first two rules which end up to be $a^n(BC)^n$.

$$ S \Rightarrow^* a^{n-1}S(BC)^{n-1} \Rightarrow a^{n-1} aBC (BC)^{n-1} = a^n (BC)^n.$$

It's quite obvious until there. My lecture than adds the third rule to $a^n(BC)^n$:

$$ a^n(BC)^n \Rightarrow^* a^nB^nC^n. $$

And that's where I'm completely lost. How is the third rule applied if its left-hand side ($CB$) isn't even part of the initial word ($a^n(BC)^n$)?


When we write $a^n(BC)^n$, we mean the word composed of $n$ copies of $a$ followed by $n$ copies of $BC$; using $^n$ is just a shortcut. For example, $a^2(BC)^2$ is shortcut for the word $aaBCBC$. Indeed, $^n$ just doesn't belong to the syntax of words, which states that a word is a sequence of terminals and non-terminals.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.