Editing Context-free grammar (section)

== Regular grammars ==
{{main|Regular grammar}}
Every [[regular grammar]] is context-free, but not all context-free grammars are regular.<ref>{{cite book |last1=Aho |first1=Alfred Vaino |last2=Lam |first2=Monica S. |last3=Sethi |first3=Ravi |last4=Ullman |first4=Jeffrey David |author-link1=Alfred Aho |author-link2=Monica S. Lam |author-link3=Ravi Sethi |author-link4=Jeffrey Ullman |title=Compilers: Principles, Techniques, & Tools |date=2007 |publisher=Pearson Addison-Wesley |location=Boston, MA USA |isbn=9780321486813 |pages=[https://archive.org/details/compilers00alfr_0/page/205 205–206] |edition=2nd |chapter-url=https://www.pearson.com/us/higher-education/program/Aho-Compilers-Principles-Techniques-and-Tools-2nd-Edition/PGM167067.html |language=en |chapter-format=print |chapter=4.2.7 Context-Free Grammars Versus Regular Expressions |quote=Every construct that can be described by a regular expression can be described by a [context-free] grammar, but not vice-versa. |url=https://archive.org/details/compilers00alfr_0/page/205 }}</ref> The following context-free grammar, for example, is also regular.
: {{math|''S'' → a}}
: {{math|''S'' → a''S''}}
: {{math|''S'' → b''S''}}

The terminals here are {{math|a}} and {{math|b}}, while the only nonterminal is {{math|''S''}}.
The language described is all nonempty strings of {{math|a}}s and {{math|b}}s that end in {{math|a}}.

This grammar is [[regular grammar|regular]]: no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.

Every regular grammar corresponds directly to a [[nondeterministic finite automaton]], so we know that this is a [[regular language]].

Using vertical bars, the grammar above can be described more tersely as follows:
: {{math|''S'' → a {{!}} a''S'' {{!}} b''S''}}