regular-grammar

Parent: regular-languages

The generative face of the regular class — rules that produce the strings (vs a machine that recognizes them).

Right-linear grammar

Productions have a single terminal-prefixed right-hand side with at most one nonterminal, on the right: A → a B and A → a (and optionally A → ε). Derive by rewriting from the start symbol until only terminals remain.

Example (binary strings ending in 1): S → 0S | 1S | 1.

Why it's exactly a finite automaton

The form A → a B means "emit a, then continue as B" — i.e. a transition A --a--> B in an NFA; A → a (or A → ε) marks an accepting move. So:

• nonterminals = states, S = start;
• A → aB = a labelled transition;
• terminal-only rules = acceptance.

Reading a derivation off left to right is running the automaton. (Left-linear grammars A → Ba are equally powerful — they build the string in reverse.)

This is the third of the three formalisms; the equivalence with regex and automata is its own article.