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