1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.)

| cite | improve this answer | |
$\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.