A binary integer can be specified by a regular grammar:
| < S> | &rarr | 0 < S> |
| < S> | &rarr | 1 < S> |
| < S> | &rarr | 0 |
| < S> | &rarr | 1 |
The following is a parse tree for the string 110101. Note that the tree is linear in form; this is the case for any regular language.
S
/ \
1 S
/ \
1 S
/ \
0 S
/ \
1 S
/ \
0 S
/
1