B Ab,
is not regular. Although every production is either in right-linear or left-linear
form, the grammar itself is neither right-linear nor left-linear, and therefore is not
regular. The grammar is an example of a linear grammar.
A linear grammar is a grammar in which at most one variable can occur on the
right side of any production, without restriction on the position of this variable.
Clearly, a regular grammar is always linear, but not all linear grammars are
regular
Our next goal will be to show that regular grammars are associated with
regular languages and that for every regular language there is a regular grammar.
Thus, regular grammars are another way of talking about regular languages.
Right-Linear
Grammars
Generate
Regular
Languages
First, we show that a language generated by a right-linear grammar is always
regular. To do so, we construct an nfa that mimics the derivations of a right
linear grammar. Note that the sentential forms of a right-linear grammar have the
special form in which there is exactly one variable and it occurs as the rightmost
symbol. Suppose now that we have a step in a derivation
ab…cD⇒ab…cdE,
arrived at by using a production D dE. The corresponding nfa can imitate this
step by going from state D to state E when a symbol d is encountered. In this
scheme, the state of the automaton corresponds to the variable in the sentential
form, while the part of the string already processed is identical to the terminal
prefix of the sentential form. This simple idea is the basis for the following
theorem.
Theorem 3.3
Let G =(V, T, S, P) be a right-linear grammar. Then L (G) is a regular language.
Proof: We assume that V = { V 0 ,V 1 ,…}, that S = V 0 , and that we have
is not regular. Although every production is either in right-linear or left-linear
form, the grammar itself is neither right-linear nor left-linear, and therefore is not
regular. The grammar is an example of a linear grammar.
A linear grammar is a grammar in which at most one variable can occur on the
right side of any production, without restriction on the position of this variable.
Clearly, a regular grammar is always linear, but not all linear grammars are
regular
Our next goal will be to show that regular grammars are associated with
regular languages and that for every regular language there is a regular grammar.
Thus, regular grammars are another way of talking about regular languages.
Right-Linear
Grammars
Generate
Regular
Languages
First, we show that a language generated by a right-linear grammar is always
regular. To do so, we construct an nfa that mimics the derivations of a right
linear grammar. Note that the sentential forms of a right-linear grammar have the
special form in which there is exactly one variable and it occurs as the rightmost
symbol. Suppose now that we have a step in a derivation
ab…cD⇒ab…cdE,
arrived at by using a production D dE. The corresponding nfa can imitate this
step by going from state D to state E when a symbol d is encountered. In this
scheme, the state of the automaton corresponds to the variable in the sentential
form, while the part of the string already processed is identical to the terminal
prefix of the sentential form. This simple idea is the basis for the following
theorem.
Theorem 3.3
Let G =(V, T, S, P) be a right-linear grammar. Then L (G) is a regular language.
Proof: We assume that V = { V 0 ,V 1 ,…}, that S = V 0 , and that we have