Editing Regular grammar (section)

== Extended regular grammars ==

An ''extended right-regular grammar'' is one in which all rules obey one of
# ''A'' → ''w'', where ''A'' is a non-terminal in ''N'' and ''w'' is in a (possibly empty) string of terminals Σ<sup>*</sup>
# ''A'' → ''wB'', where ''A'' and ''B'' are in ''N'' and ''w'' is in Σ<sup>*</sup>.

Some authors call this type of grammar a ''right-regular grammar'' (or ''right-linear grammar'')<ref>{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }} Here: p.217 (left, right-regular grammars as subclasses of [[context-free grammar]]s), p.79 (context-free grammars)</ref> and the type above a ''strictly right-regular grammar'' (or ''strictly right-linear grammar'').<ref>Hopcroft and Ullman 1979 (p.229, exercise 9.2) call it a normal form for right-linear grammars.</ref>

An ''extended left-regular grammar'' is one in which all rules obey one of
# ''A'' → ''w'', where ''A'' is a non-terminal in ''N'' and ''w'' is in Σ<sup>*</sup>
# ''A'' → ''Bw'', where ''A'' and ''B'' are in ''N'' and ''w'' is in Σ<sup>*</sup>.