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.
Trouble understanding Grammar Rules
formal grammars;notation
$(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$