Er følgende grammatikk regulær?
Gitt en grammatikk med terminalsymboler $\str{a}$ og $\str{b}$, ikke-terminalsymboler $S$, $A$ og $B$, startsymbol $S$ og produksjonsregler
Ja, grammatikken er regulær fordi alle produksjonsreglene er på formen $A \rightarrow X$, hvor $A$ er et ikke-terminalsymbol og $X$ består av maksimalt ett ikke-terminalsymbol som i så fall forekommer lengst til høyre. (Husk at $A \rightarrow \str{a}A \mid B$ er en forkortelse for de to produksjonsreglene $A \rightarrow \str{a}A$ og $A \rightarrow B$.)
Språket som defineres av grammatikken beskrives også av det regulære uttrykket $\str{aa}\str{a}\xx\str{b}\xx$.
Hvilke av disse grammatikkene er regulære?
Her forekommer ikke-terminalsymbolet i produksjonsregelen $S \rightarrow \str{a}S\str{b}$ lengst til høyre, og derfor er ikke dette en regulær grammatikk.
Her er det maksimalt ett ikke-terminalsymbol i hver produksjonsregel, og alle ikke-terminalsymbolene forekommer lengst til høyre på høyresiden av $\rightarrow$. Dette er altså en regulær grammatikk.
Dette er ikke en regulær grammatikk, siden den første produksjonsregelen har to ikke-terminalsymboler, og en regulær grammatikk kan maksimalt ha ett slik symbol i hver produksjonsregel.
Dette er en regulær grammatikk, siden det enten er ingen eller ett ikke-terminalsymbol i hver produksjonsregel, og alle ikke-terminalsymbolene forekommer lengst til høyre.