1

Suppose we have the rules:

$R \rightarrow XRX | S$

$S \rightarrow aTb | bTa$

$T \rightarrow XTX | X | \epsilon$

$X \rightarrow a | b$.

My textbook says that $T \stackrel{*}\implies T$ is possible. Could this be a mistake because I am almost certain this cannot be. Or else I must not be understanding correctly.

Start with $T$. We have three choices

$T \implies XTX$. But now that we have $X$ involved, we will have $a's$ and/or $b's$ involved.

$T \implies X$. Again we will have $a$ or $b$ involved.

$T \implies \epsilon$. But $\epsilon \not= T$.

This is exercise 2.3 (i) in Michael Sipser's Theory of Computation 3rd edition (not homework)

Joseph DiNatale
  • 2,845
  • 22
  • 36
  • $a$ and $b$ are the only terminals, right (well and the empty string, $\varepsilon$)? – Jared Apr 08 '14 at 21:03
  • That is correct, sorry I did not state that, but the problem does not state it either. – Joseph DiNatale Apr 08 '14 at 21:05
  • 1
    This may help: http://stackoverflow.com/questions/7814904/what-are-these-arrow-operators-in-context-free-grammar I think the key is the empty string. A valid sentence can be nothing, which $T$ produces with $0$ or more productions of $T \rightarrow \varepsilon$ (in fact, it could be as many $T \rightarrow \varepsilon$'s as you like). – Jared Apr 08 '14 at 21:12
  • I understand now. My book states that $u \implies v$ if $u = v$. Hence $T \implies T$. – Joseph DiNatale Apr 08 '14 at 21:14

1 Answers1

1

I think this is notation problem:

  • The star in $X\stackrel{*}\Longrightarrow Y$ denotes zero or more steps. In other words $T \stackrel{*}\Longrightarrow T$ is true, because relation $\stackrel{*}\Longrightarrow$ is reflexive. You can think about it a bit like $\leq$ relation (depending on the grammar it might actually be a non-strict partial order).
  • On the other hand, $X\stackrel{+}\Longrightarrow Y$ denotes one or more steps and in result $T\stackrel{+}\Longrightarrow T$ is in your case false. You can think of it a bit like the strict version $<$ (depending on the grammar it might actually be a strict partial order).

I hope this helps $\ddot\smile$

dtldarek
  • 37,381