CS 301 - Theory of Computation - L16

This lecture introduces an algorithm to generate a Right Linear Grammar (Regular Grammar) from an NFA with epsilon transitions and hence establishes that there exists a Right Linear Grammar for any Regular Language.  Also, it discusses an algorithm to generate an NFA with epsilon transitions from Left Linear Grammar and hence establishes that the language represented by an arbitrary Left Linear Grammar is Regular.