If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \{c\}$ the set of non-terminals?

These notations are used here, p. 379. But I cannot find their definitions.

So what I'm asking is, is the above a reasonable interpretation?


No. $\Sigma$ is the set of symbols that the strings in the two languages are over ("the alphabet"). So $c$ is one symbol, and $Y$ is the set of all the other symbols in the alphabet. These will all be terminals when the CFG is constructed in the proof.

What the theorem is saying is that if you have a context-free language $L$ that uses only symbols from $Y$, then $L$ is also regular if and only if the new language where you prepend a $c$ to every string in $L$ (i.e. $cL$) is also regular.

At this point there's no mention of a CFG, so there's no terminals or nonterminals. The proof is where the CFG is introduced as a consequence of $L$ being context-free. Note however that this proof is very very truncated, there's a lot of detail and reasoning left out, so it's a lot harder to follow than it should be if you don't already see the reason that the theorem is true. There's also a series of mistakes in it.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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