1
$\begingroup$

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?

  • 0
    You can make $\stackrel{*}{\Rightarrow}$ in $\LaTeX$ using `\stackrel{*}{\Rightarrow}`.2012-10-07

2 Answers 2

7

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

4

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