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.

  • 1
    $\begingroup$ You have two very different things represented by the same letter P: The set of rules, and a variable. You last rules says that we can replace $P\in V \subseteq (V\cup \Sigma)^+$ by $0P0\in \Sigma V \Sigma \subseteq (V\cup \Sigma)^*$. And also, rules are elements of the cartesian product (not subsets). $\endgroup$
    – xavierm02
    Apr 26, 2017 at 12:20

1 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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