Trouble understanding Grammar Rules

Question

I am totaly new to theoretical computer science, so I am sorry if I get the terminology wrong:

I was reading the definition of a grammar, what I didn't get was the formal definition of the production rules: Let V be the set of Variables and sigma the alphabet. Let P be the set of Rules or productions. Formal: $P \subset (V \cup\sum)^+\times (V \cup\sum)^*$.

I saw an example with G = ({P}, {0,1}, A, P) with the set of rules A:

1.P $\to \epsilon$

2.P $\to 0$

2.P $\to 1$

4.2.P $\to 0P0$

Now my question: How can the last rule (no 4) exist? It is not an element of the subset of the cartesian product mentioned above.

Answer 1

$(V\cup\Sigma)$ represents the set of variables (like $P$) and terminals (like $0$).

$(V\cup\Sigma)^*$ represents all finite strings (including the empty string) that can be made from variables and terminals (like $0P0$ or, $01P10PP0P0$, for instance). The expression $(V\cup\Sigma)^+$ is almost the same, but excludes the empty string.

Functions are essentially matchings so can be represented by a Cartesian product $(x, f(x))$, so in your definition, a production in $(V\cup\Sigma)^+\times(V\cup\Sigma)^*$ is a pairing from nonempty strings to strings, like the ones you gave. Others would include

• $V\rightarrow \epsilon$ (the empty string is often denoted by $\epsilon$ or $\lambda$).
• $S\rightarrow 01001$, or even
• $aT\rightarrow TbT$