Search code examples
computer-sciencecontext-free-grammar

Why is T⇒T false, but T⇒∗T true?

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


1) T⇒T
2) T⇒∗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. Can someone show me the process for T⇒∗T.

Solution

  • The operator ⇒ means "exactly one production". It is true that there is no single production that takes T to T.

    The operator ⇒* means "any number of productions". Any number includes zero. Because zero productions doesn't take the LHS anywhere, the LHS always ⇒*'s itself (thanks to rici to pointing out an incorrect rendering in the original post).

    My sense is that ⇒* is defined this way to make some aspects of its usage more streamlined than if it meant "at least one".