Explanation of math statement

Question

This symbols are used to describe left recursion :

$A\to B\,\alpha\,|\,C$
$B\to A\,\beta\,|\,D,$

It is taken from : http://en.wikipedia.org/wiki/Left_recursion

How can these symbols be explained to a non-mathematician ? Can provide an explanation for these statements in image ?

Answer 1

First of all, uppercase letters mean something which must still be worked out, while Greek letters mean actual symbols for the language. The arrow $\rightarrow$ means "if you find something like the symbols on my left, you may substitute them with the symbols on my right", and the vertical bar | means "or".

Now the first line says that if you find an $A$ you may either substitute it with $B\alpha$ or with $C$. Suppose to choose the first one; now $\alpha$ is fixed, while $B$ may be substituted with $A\beta$ (or $D$, but we won't do it).

This means that if you start with $A$ you may - note, not must - transform it to $B\alpha$ first and $A\beta\alpha$ then. It's like you have left something on your right ($\beta\alpha$) and now you are ready to start it over like if nothing happened. It's left recursion because you are going "left", and is indirect because you need more than one step.

Answer 2

This notation is used in formal language theory to describe formal grammars. A formal grammar consists of four things:

• A collection of non-terminal symbols (usually written as uppercase letters),
• a collection of terminal symbols (usually lowercase and sometimes Greek letters),
• a start symbol (which has to be one of the non-terminal symbols) and
• production rules.

It is common to use $S$ as the start symbol and to specify the non-terminal and terminal symbols implicitly as those used in the rules.

The example in the image shows some rules. Each rule consists of a head, written to the right of the arrow, and a tail, written to the left. In this case, each tail specifies two alternatives, divided by the pipe. The symbols are implicitly specified: $A$, $B$, $C$ and $D$ are non-terminal symbols, $\alpha$ and $\beta$ are terminal symbols. There is no start symbol indicated, so it probably meant to be a part of a bigger grammar.

To generate words from a grammar, you usually start with the start symbol. You may then repeatedly replace any sequence of characters in the word you generated so far with one of the alternatives in the tail of a rule, provided the replaced sequence of characters is exactly the head of that rule. When there are no more non-terminal symbols left, the word you generated is part of the formal language.

In your example, taking $A$ as the start symbol, we may replace $A$ by $B\alpha$ (by the first rule). We can then replace the $B$ by $A\beta$ (by the second rule), so our word becomes $A\beta\alpha$. Replacing $A$ by $B\alpha$ again, we get $B\alpha\beta\alpha$ and so on.

You see that we add characters to the left of our already generated word by using the same rules over and over again. Therefore, it is left recursion. If at any point we decide to replace $A$ by $C$ or $B$ by $D$, the generation stops.

(In a real-world example, there would be further rules for $C$ and $D$, but in this example there aren’t, because they are not part of the left recursion.)