$ \varepsilon $ | $ a $ | $ b $ | $ c $ | |
---|---|---|---|---|
→ $ p $ | $ \{q,r\} $ | $ \emptyset $ | $ \{q\} $ | $ \{r\} $ |
$ q $ | $ \emptyset $ | $ \{p\} $ | $ \{r\} $ | $ \{p,q\} $ |
* $ r $ | $ \emptyset $ | $ \emptyset $ | $ \emptyset $ | $ \emptyset $ |
0 | 1 | |
---|---|---|
→ A | B | E |
B | C | F |
* C | D | H |
D | E | H |
E | F | I |
* F | G | B |
G | H | B |
H | I | C |
I | A | E |
$$ \begin{array}{rcl} S & \rightarrow & 0 S 1 \; | \; A \\ A & \rightarrow & 1 A 0 \; | \; S \; | \; \varepsilon \\ \end{array} $$
$$ P \; = \; (\{p,q\}, \{0,1\}, \{X, Z_0\}, \delta, q, Z_0)$$ $$ \begin{array}{rcl} \delta (q, 1, Z_0) & = & \{ (q, X Z_0) \} \\ \delta (q, 1, X) & = & \{ (q, X X) \} \\ \delta (q, 0, X) & = & \{ (p, X) \} \\ \delta (q, \varepsilon, X) & = & \{ (q, \varepsilon) \} \\ \delta (p, 1, X) & = & \{ (p, \varepsilon) \} \\ \delta (p, 0, Z_0) & = & \{ (q, Z_0) \} \\ \end{array} $$
$$ \begin{array}{rcl} S & \rightarrow & aAa \; | \; bBb \; | \; \varepsilon \\ A & \rightarrow & C \; | \; a \\ B & \rightarrow & C \; | \; b \\ C & \rightarrow & CDE \; | \; \varepsilon \\ D & \rightarrow & A \; | \; B \; | \; ab \\ \end{array} $$
$$ \begin{array}{rcl} S & \rightarrow & AB \; | \; BC \\ A & \rightarrow & BA \; | \; a \\ B & \rightarrow & CC \; | \; b \\ C & \rightarrow & AB \; | \; a \\ \end{array} $$