需要帮助查找这些语言的上下文无关语法

Question

我需要帮助找到这些语言的语法。 我觉得这些解决方案一事无成

1) {a^h b^k a^m b^n | h + k = m + n}

2) {a^i b^j a^k | (i = j 和 k ≥ 0) 或 (i ≥ 0 和 j> k)}

任何帮助将不胜感激

Answer 1

我假设你正在寻找上下文无关的语法。我将使用约定，S是根生产规则，大写单词是规则(如S、AB、A等)，空生产写empty，文字写成'a'和'b'。

第一种语法是：

S := AB
AB := 'a' AB 'b' | AA | BB
AA := 'a' AA 'a' | BA
BB := 'b' BB 'b' | BA
BA := 'b' BA 'a' | empty

这里的诀窍是要意识到，要保持两半的长度相同，必须定义在两侧添加一个符号的语法产品。然后要注意，我们首先

在左边添加"a"，在右边添加"b"，然后我们继续在两侧添加"a"，或向两侧添加"b"，最后继续在左边添加"b"，在右边添加"a"。第二种语法是：

S := AB A | A B BA
AB := 'a' AB 'b' | empty
A := 'a' A | empty
B := 'b' B | 'b'
BA := 'b' BA 'a' | empty

这比第一种更容易：根生产已经作为两件事的选择给出，所以很自然地在规则中表达出来。第一个选择是生成一定数量的"a"，然后是相同数量的"b"，然后是任意数量的"a"。第二种选择是生成一定数量的"a"，然后生成一些正数的"b"，然后生成相等数量的"b"和"a"。这保证了该选择的描述中的"j>k"。

这里的语法都不是明确的，尽管消除歧义只是稍微复杂一些。