Why is $T \Rightarrow T$ false, but $T \stackrel{*}{\Rightarrow} T$ true? I'm not sure how to derived this.

Question

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | ε (empty string)
X -> a | b

1. $T \Rightarrow T$
2. $T \stackrel{*}{\Rightarrow} T$

I know the first one is false since you cannot derived it to T but for the second one my friend said it is true while I thought it is false. I was wondering how do you eventually derived from T to T.

Answer 1

The star in $\overset{*}\Rightarrow$ works like the Kleene star in regular expressions: it includes $\overset{n}\Rightarrow$ for all $n\ge 0$, so it includes $0$-step derivations $u\Rightarrow v$ in which $u=v$. You’re correct in thinking that there is no derivation of $T$ from $T$ that actually uses at least one production.