A grammar whose language is a set of even numbers

Question

I want to construct a context free grammar for a language which is a set of even numbers. Here is my attempt

s:> 0T0|T2T4T6T8|£

where £ is an empty string

T:> 2|4|6|8|

please i need something better than this

Answer 1

This answer assumes that you want the numbers to appear in a canonical form, i.e. without leading zero-digits.

The set of decimal representations of even numbers is equivalent to the union of $\left\{0\right\}$ and the set of digit streams beginning with $\left\{1,2,3,4,5,6,7,8,9\right\}$ and ending with $\left\{0, 2, 4, 6, 8\right\}$. This is a Strictly Local (and thus Regular) stringset. Any Regular stringset can be recognized (or generated) by a left- or right-linear CFG. A left-linear grammar for this particular set is:

$$\begin{align} S &\to T0 \mathrel{|} T2 \mathrel{|} T4 \mathrel{|} T6 \mathrel{|} T8\\ T &\to U \mathrel{|} \varepsilon\\ U &\to U0 \mathrel{|} T1 \mathrel{|} T2 \mathrel{|} T3 \mathrel{|} T4 \mathrel{|} T5 \mathrel{|} T6 \mathrel{|} T7 \mathrel{|} T8 \mathrel{|} T9 \end{align}$$

This essentially builds strings from the right. $S$ begins the process by rewriting to a $T$ followed by an even digit. Since the final digit is even, the generated number will be even no matter what $T$ rewrites to. The job of $T$ is to decide whether to terminate the string (by becoming $\varepsilon$) or place more digits (by becoming $U$).

Whenever $U$ appears, it will continue generating the number by placing one additional digit. If that digit is a (leading) zero, it is preceded by another $U$, else by a $T$. Since $U$ must place at least one digit, this prevents generation of leading zeroes.

Suppose you want to generate $2048$. A derivation follows:

$$\begin{align} \color{red}{S} &\to \color{red}{T8}\\ \color{red}{T}8 &\to \color{red}{U}8\\ \color{red}{U}8 &\to \color{red}{T4}8\\ \color{red}{T}48 &\to \color{red}{U}48\\ \color{red}{U}48 &\to \color{red}{U0}48\\ \color{red}{U}048 &\to \color{red}{T2}048\\ \color{red}{T}2048 &\to \color{red}{\varepsilon}2048\\ \color{red}{\varepsilon}2048 &=2048 \end{align}$$