How is this derivation possible in a context-free grammar?

Question

Suppose we have the rules:

$R \rightarrow XRX | S$

$S \rightarrow aTb | bTa$

$T \rightarrow XTX | X | \epsilon$

$X \rightarrow a | b$.

My textbook says that $T \stackrel{*}\implies T$ is possible. Could this be a mistake because I am almost certain this cannot be. Or else I must not be understanding correctly.

Start with $T$. We have three choices

$T \implies XTX$. But now that we have $X$ involved, we will have $a's$ and/or $b's$ involved.

$T \implies X$. Again we will have $a$ or $b$ involved.

$T \implies \epsilon$. But $\epsilon \not= T$.

This is exercise 2.3 (i) in Michael Sipser's Theory of Computation 3rd edition (not homework)

Answer 1

I think this is notation problem:

• The star in $X\stackrel{*}\Longrightarrow Y$ denotes zero or more steps. In other words $T \stackrel{*}\Longrightarrow T$ is true, because relation $\stackrel{*}\Longrightarrow$ is reflexive. You can think about it a bit like $\leq$ relation (depending on the grammar it might actually be a non-strict partial order).
• On the other hand, $X\stackrel{+}\Longrightarrow Y$ denotes one or more steps and in result $T\stackrel{+}\Longrightarrow T$ is in your case false. You can think of it a bit like the strict version $<$ (depending on the grammar it might actually be a strict partial order).

I hope this helps $\ddot\smile$