// g_220v.g  Regular (linear) Grammar for a DFA  Book p220
//
// Given DFA M = (Q, Sigma, delta, q0, F)
//       Q = { A, B, C, D }
//       Sigma = { 0, 1 }
//       q0 = A
//       F = { B }
//
// delta | 0 | 1 |
// ------+---+---+
//     A | B | D |
//     B | D | C |
//     C | B | D |
//     D | D | D |
//
//
//      The regular expression for this DFA is  0(10)*
//
// Create Regular Grammar G = (V, T, P, S)
//      V = Q = { A, B, C, D }
//      T = Sigma = { 0, 1 }
//      S = q0 = A
//
// P = productions from transitions plus transitions to final states, F
//
//   delta(A,0)=B makes production  A -> 0 B
//   delta(A,1)=D makes production  A -> 1 D   etc.
//
//   delta(C,0)=B where B is in F, makes production   C -> 0  etc.
//

verbose 3
start A
variable A B C D ;
terminal 0 1 ;

A -> 0 B ;
A -> 1 D ;
A -> 0   ; // to final state
B -> 0 D ;
B -> 1 C ;
C -> 0 B ;
C -> 1 D ;
C -> 0   ; // to final state
D -> 0 D ;
D -> 1 D ;

enddef
0
010
01010
111
011