Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
You can make $\stackrel{*}{\Rightarrow}$ in $\LaTeX$ using \stackrel{*}{\Rightarrow}. –  Ayman Hourieh Oct 7 '12 at 18:30
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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