0
$\begingroup$

So, I have a book here, which has an example for context sensitive grammar, and the grammar is the famous $0^n1^n2^n$ , and it has:

$$ \begin{align} S &\rightarrow 0BS2 \mid 012 \\ B0 &\rightarrow 0B \\ B1 &\rightarrow 11 \\ \end{align} $$

I agree that the above works, but what is wrong with just saying: $S\rightarrow 0S12 |\epsilon$

The above also generators the same number of $0$s as $1$s and $2$s.

$\endgroup$
5
$\begingroup$

Your grammar will generate: $S\rightarrow 0S12\rightarrow 00S1212\rightarrow 001212$ which is not in the required language.

$\endgroup$
2
$\begingroup$

By one definition, context sensitive grammars have productions $\alpha \rightarrow \beta$, where the length of $\beta$ can't be less than the length of $\alpha$. This rules out your alternative grammar outright.

$\endgroup$

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.