Search code examples
context-free-grammarlexicalcontext-free-language

Context free grammar syntax

I'm trying to clarify the following about context-free grammar:

If I've got the following,

S->T0T

If there are two possible values for T ie.

T-> 1T | 1

Do I have to use the same value when substituting both Ts, like so:

T0T becomes (1T)0(1T) => 1T01T

Or can I use different values for each T, like so:

TOT becomes (1T)0(1) => 1T01
Solution

  • There is no relationship between the two Ts. The restriction that they had to be the same would make the grammar not context-free, since the replacement of T in a context-free grammar is independent of the context. Hence "context-free".