# Why is $T \Rightarrow aba$ false, but $T \stackrel{*}{\Rightarrow}$ true?

I am reading Sipser's book and encountered a question with this regular grammer:

$$R \Rightarrow XRX~|~S \\ S \Rightarrow aTa~|~bTa \\ T \Rightarrow XTX~|~X~|~\varepsilon \\ X \Rightarrow a~|~b$$

Apparently, the solutions in the back say that $T \Rightarrow aba$ is false. Why? Isn't this a derivation for $aba$?

$$T \Rightarrow XTX \Rightarrow aTa \Rightarrow aXa \Rightarrow aba$$

On the other hand, $T \Rightarrow aba$, where the arrow has an asterisk on top of the arrow (I'm not sure how to make this symbol in LateX), is true. Why is there a difference?

-
You can make $\stackrel{*}{\Rightarrow}$ in $\LaTeX$ using \stackrel{*}{\Rightarrow}. –  Ayman Hourieh Oct 7 '12 at 18:30

According to Sipser, the $u \Rightarrow v$ notation means that after a single step you can obtain $v$ from $u$ (applying a single rule to a single variable in $u$).

On the other hand $u \Rightarrow^* v$ means that after some number of steps you can obtain $v$ from $u$.

So $T \not\Rightarrow aba$ since the only strings you can obtain from $T$ after a single step are $$XTX; \quad X; \quad \varepsilon.$$

-
$T \stackrel{*}{\Rightarrow} aba$ means that you can derive $aba$ from $T$ after applying grammar rules one or more times (as you did in your question). On the other hand, $\Rightarrow$ (without the asterisk), means that the derivation happens in only one step.