* 17. Analogous to the previous exercise, consider all words that can be formed
from L by dropping a single symbol of the string. Formally define this
operation drop for languages. Construct an nfa for drop (L), given an nfa for
L.
18. Use the construction in Theorem 3.1 to find nfa's for L (aØ)and L (Ø*). Is
the result consistent with the definition of these languages?
3.3 Regular Grammars
A third way of describing regular languages is by means of certain grammars.
Grammars are often an alternative way of specifying languages. Whenever we
define a language family through an automaton or in some other way, we are
interested in knowing what kind of grammar we can associate with the family.
First, we look at grammars that generate regular languages.
Right-and Left-Linear Grammars
Definition 3.3
A grammar G =(V, T, S, P) is said to be right-linear if all productions are of the
form
A → xB,
A → x,
where A, B ∈ V, and x ∈ T*. A grammar is said to be left-linear if all
productions are of the form
A → Bx,
or
A → x.
A regular grammar is one that is either right-linear or left-linear.