A linear grammar is one in which every rule has exactly one terminal and one non-terminal on the right hand side or just

a single terminal on the right hand side or the empty string. ex)

S --> aS | a | bB; B --> bB | b.

1. Prove that any regular language can be generated by a linear grammar. Construct a grammar from a DFA. Or, you can give a straight-

forward proof that the language generated by the grammar and the language recognized by the DFA are the same.

2. Is every language generated by a linear grammar regular? If yes, give a proof. If no, give an example.