离散数学中的正则文法

正规语言可以通过正规文法生成。在正规文法中，左侧始终只包含一个非终结符。左侧不能包含多个非终结符或任何终结符变量。右侧可以是一个终结符或一个后跟非终结符的终结符。

正规文法的产生式将是以下形式

其中

X 和 Y 用来表示变量 (V)。

'x' 用来表示终结符串 (T*)

正规文法的类型

正规文法有两种类型，描述如下

• 左线性文法 (LLG)
• 右线性文法 (RLG)

左线性文法

在左线性文法中，产生式必须是以下形式。

其中

X、Y 属于变量 (V)，'x' 属于 T*。

右线性文法

在右线性文法中，产生式必须是以下形式。

其中

X、Y 属于变量 (V)，'x' 属于 T*。

正规语言可以被描述为由 3 型文法生成且可以设计有限自动机的语言。它可以将 FA 转换为 3 型文法。

示例：在本例中，我们将演示接受以符号 y 开头的字符串的有限自动机。

与 FA 对应的右线性文法描述如下

正如我们所见，上述文法是右线性文法。该文法可以直接通过有限自动机编写。

可以通过上述 RLG 生成一个字符串，该字符串以 b 开头。在 b 之后，该字符串可以接受任何输入符号（即 ∑ = {x, y}）。

如果我们反转上述右线性文法 (RLG) 的产生式，我们将得到以下文法

该文法推导出所有以 b 结尾的字符串的语言，描述如下

总而言之，我们可以说，假设我们有一个代表语言 L 的有限自动机，我们将其转换为右线性文法，它也代表相同的语言 L。在这种情况下，当我们反转 RLG（右线性文法）时，我们将得到代表语言 L' 的左线性文法，L' 是 L 的反向。

RLG 转换为 LLG

当我们将右线性文法转换为语言 L 的左线性文法时，将使用以下步骤。

步骤 1：对于语言 L，我们必须反转 FA（有限自动机）。

步骤 2：之后，我们必须为它编写右线性文法。

步骤 3：现在，我们将反转 RLG。

完成步骤 3 后，我们将得到生成语言的文法，该文法能够代表同一语言 L 的左线性文法。

此处 L 用于描述 FA（有限自动机）的语言，L^R 用于描述语言 L 的反向。

示例

在本例中，我们将使用上述代表语言 L 的有限自动机，并接受所有以符号 y 开头的字符串。该语言包含输入符号（即 ∑ = {x, y}）。这里我们将此自动机转换为左线性文法。

解决方案

步骤 1：有限自动机的反向描述如下

步骤 2：对于此反向 FA，相应的右线性文法描述如下

步骤 3

现在我们将反转上述右线性文法并得到以下文法

所以这个文法是左线性文法，用于表示所有以符号 y 开头的字符串。所以

RLG（右线性文法）转换为 FA（有限自动机）

我们将从第一个产生式开始。

对于每个左变量/字母，我们将转到其后的符号。

起始状态：第一个产生式状态称为起始状态。

终止状态：所有以终结符结尾而没有进一步非终结符的状态。

示例

在本例中，我们有语言 L 的右线性文法。该文法表示所有以 0 结尾的字符串。

因此，与右线性文法对应的有限自动机描述如下

这里我们将从变量 X 开始并像这样使用它的产生式

• 产生式 X → 0X 意味着当转换将 '0' 作为输入符号时，状态转换将始终保持在同一状态 X。
• 产生式 X → 1Y 意味着当转换将 '1' 作为输入符号时，状态转换将从状态 X 转到状态 Y。
• 产生式 X → 0Y 意味着当转换将 '0' 作为输入符号时，状态转换将从状态 X 转到状态 Y。
• 产生式 Y → ∈ 意味着此状态不需要任何类型的状态转换。在相应的 FA（有限自动机）中，这种产生式将是终止状态，因为其 RHS 是终结符。

因此，对于相应的右线性文法，最终的 NFA（非确定性有限自动机）描述如下

LLG 转换为 FA

说明

这里我们首先将 LLG 转换为 RLF 文法。这里的 LLG（左线性文法）代表语言 L，而 RLG（右线性文法）代表语言 L 的反向，即 L^R。之后，我们将设计对应于此反向语言 (L^R) 的 FA。之后，我们将反转有限自动机 (FA)。反向 FA 是语言 L 的最终 FA。

LLG 转换为 RLG

为了解释这一点，我们将使用上述文法，该文法用于表示语言 L，并接受所有以变量 y 开头的字符串集合。此文法的左线性文法描述如下

步骤 1

在此步骤中，我们将 LLG 转换为 FA。转换过程与上述相同。所以

步骤 2

在此步骤中，我们将反转 FA。这意味着我们将初始状态转换为终止状态，并将终止状态转换为起始状态。我们还将像这样反转所有边

步骤 3

在此步骤中，我们将编写对应于反向有限自动机的 RLG。