// g_reg.g  regular grammar (linear) grammar
//
// Machine Definition  M = (Q, Sigma, alpha, q0, F)
// Q = { q0, q1, q2, q3, q4 } the set of states
// Sigma = { 0, 1 }           the input string alphabet
// q0 = q0                    the starting state
// F = { q2, q4 }             the set of final states (accepting)
//
//                          inputs
//   alpha          |    0    |    1    |
//         ---------+---------+---------+
//              q0  |   q3    |   q1    |
//              q1  |   q1    |   q2    |
//    states    q2  |   q2    |   q2    |
//              q3  |   q4    |   q3    |
//              q4  |   q4    |   q4    |
//
// L(M) is the notation for a Formal Language defined by a machine M.
// Some of the shortest strings in L(M) = { 00, 11, 000, 001, 010, 101, 110,
// 111,  0000, 00001, ... }
//
//  The regular expression for the machine M above is
//    r = (1(0*)1(0+1)*)+(0(1*)0(0+1)*)
//
//  The equivalent regular grammar is constructed from  M
//
//  G = ( V, T, P, S )
//  V = { q0, q1, q2, q3, q4 }  Q of M
//  T = { 0, 1 }                Sigma of M
//  S = { q0 }                  q0 of M


start q0
variable q0 q1 q2 q3 q4 ;
terminal 0 1 ;

//  construct the productions P from alpha:
//  delta(qi,a) = qj  becomes rule   qi -> a qj

// also, every state, qi, that transitions to a final state on a, gets qi -> a
// and if q0 is a final state of M,  q0 -> epsilon.
// (an optional rule is for every final state, qi in F, qi -> epsilon)

q0 -> 0 q3 ;
q0 -> 1 q1 ;
q1 -> 0 q1 ;
q1 -> 1 q2 ;
q1 -> 1    ; // goes to a final state
q2 -> 0 q2 ;
q2 -> 1 q2 ;
q2 -> 0    ; // goes to a final state
q2 -> 1    ; // goes to a final state
q3 -> 0 q4 ;
q3 -> 1 q3 ;
q3 -> 0    ; // goes to a final state
q4 -> 0 q4 ;
q4 -> 1 q4 ;
q4 -> 0    ; // goes to a final state
q4 -> 1    ; // goes to a final state

enddef
0110
10100111
0111
1000