正则文法

上级：regular-languages

这是正则类生成式的一面——用规则去生成字符串（相对于用一台机器去识别它们）。

右线性文法

每条产生式的右侧都是单个以终结符打头的形式，最多带一个非终结符，且非终结符在最右边： A → a B 以及 A → a（可以有 A → ε）。 推导的做法是从起始符号开始不断改写，直到只剩终结符。

例（以 1 结尾的二进制串）：S → 0S | 1S | 1。

为什么它恰好就是有限自动机

A → a B 这个形式的意思是"发出 a，然后继续作为 B"——也就是 NFA 里的一个转移 A --a--> B；A → a（或 A → ε）标记一次接受动作。于是：

• 非终结符 = 状态，S = 起始状态；
• A → aB = 一条带标签的转移；
• 只含终结符的规则 = 接受。

从左到右读一次推导，就是在跑这台自动机。（左线性文法 A → Ba 能力相同——只是把字符串反着构建。）

这是三种形式化方式中的第三种；它与正则表达式、自动机之间的等价性是另一篇文章的内容。