Section: Finite Automata
def. Right Linearity. A grammar is right-linear iff all elements in the range of the production rules only contain variables on the right side of the result; i.e.:
Observe that a right-linear grammer is same as being able to extend it only on the right. Left-linear grammar is vice versa
def. A Regular Grammar is a grammar that is exclusively either right-linear or left-linear.
RegGrammar DFA
pf. Regular Grammar ⇒ DFA
for , for each rule in , convert a variable into a state; arcs identify the rightside (or leftside) terminal variable
pf. DFA ⇒ Regular Grammar