Homework #$7$ due December $26,2023$ before recitation

Question $1$

A CFG is called right linear if all productions are of the form $AaB$ or $Ae$ and called left

linear if all productions are of the form $ABa$ or $Ae$ where $A,$BinV and ainT and $e$ is the

empty string.

Show that both right linear and left linear grammars generate regular languages. Specify finite

state machines corresponding respectively to right and left linear grammars.

Main Text: Exercise $7\mathrm{.}1\mathrm{.}3,7\mathrm{.}1\mathrm{.}4,7\mathrm{.}2\mathrm{.}1($b$),($c$),7\mathrm{.}4\mathrm{.}3($b$),($c$)$