I'm trying to build a regular grammar to generate the valid movements for the knight. I'm using (U)p, (D)own, (L)eft, (R)ight to represent each of the components of the movement. I already have a NFA who does the job, but I can't get to figure the grammar for the exercise.
It must look something like
S --> lL | rR | uU | dD.
L --> lL | lU | lD.
R --> rR | rU | rD.
So I can use that grammar to get to any of the 16 possible movements. (ULL, URR, UUL, UUR, DDL, DDR, DLL, DRR, LUU, LDD, LLU, LLD, RRU, RRD, RDD, RLL).
My main language is Portuguese and I don't know if the terms I'll be using are the same you guys use in english. Also, I may be messing up with my explanation, since I really don't get what I need to develop that grammar.
This would work: \begin{align} S \to & ULL \mid URR \mid UUL \mid UUR \, \mid \\ & DDL \mid DDR \mid DLL \mid DRR \, \mid \\ & LUU \mid LDD \mid LLU \mid LLD \, \mid \\ & RRU \mid RRD \mid RDD \mid RLL \end{align} More structured: \begin{align} S \to & J_1 \mid J_2 \\ J_1 \to & U_1 \mid D_1 \mid L_1 \mid R_1 \\ U_1 \to & u H_2 \\ D_1 \to & d H_2 \\ L_1 \to & l V_2 \\ R_1 \to & r V_2 \\ H_2 \to & ll \mid rr \\ V_2 \to & uu \mid dd \\ J_2 \to & U_2 \mid D_2 \mid L_2 \mid R_2 \\ U_2 \to & uu H_1 \\ D_2 \to & dd H_1 \\ L_2 \to & ll V_1 \\ R_2 \to & rr V_1 \\ H_1 \to & l \mid r \\ V_1 \to & u \mid d \end{align} Note that I now use upper case for the non-terminal symbols and lower case for the terminal ones.
More compact: \begin{align} S \to & J_1 \mid J_2 \\ J_1 \to & u H_2 \mid d H_2 \mid l V_2 \mid r V_2 \\ J_2 \to & uu H_1 \mid dd H_1 \mid ll V_1 \mid rr V_1 \\ H_1 \to & l \mid r \\ V_1 \to & u \mid d \\ H_2 \to & ll \mid rr \\ V_2 \to & uu \mid dd \\ \end{align}