In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim.

Consider the grammar:

$$ \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \to XTX \mid X \mid \epsilon \\ &X \to a \mid b \end{align*} $$

In this grammar, it holds that $T \Rightarrow^* T$.

Can anyone explain how this is true?


1 Answer 1


We say that $\alpha \Rightarrow^* \beta$ if $\beta$ can be derived from $\alpha$ in zero or more steps. (More fancily, $\Rightarrow^*$ is the reflexive-transitive closure of $\Rightarrow$.) In particular, it is always that case that $\alpha \Rightarrow^* \alpha$, for every $\alpha$, due to a derivation of zero steps.

In contrast, in your case it doesn't hold that $T \Rightarrow^+ T$. (This is derivation in one or more steps, or the transitive closure of $\Rightarrow$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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