grammar - 创建 "Context Free Grammar"的提示

Question

我是 CFG 的新手，
有人可以给我创建生成某种语言的 CFG 的提示吗

例如

L = {am bn | m >= n}

我得到的是:

So -> a | aSo | aS1 | e
S1 -> b | bS1 | e

但我认为这个区域是错误的，因为有可能是 的数量。 b 的可以大于 a 的。

Answer 1

如何使用示例 ambn 编写 CFG

L = {a^m bⁿ | m >= n}.

语言描述:上午BN由 a 随后 b 其中的 a 数相等或多于 b 的数目。

一些示例字符串: {^, a, aa, aab, aabb, aaaab, ab......}
所以总是有一个 a 一个 b 但额外的 a 可能是 _67x2感染字符串只能由 a 组成。还要注意 ^ null 是语言的成员，因为在 ^ NumberOf(a) = NumberOf(b) = 0

How to write a grammar that accepts the language formed by strings a^m bⁿ?

在语法中，应该有这样的规则，如果你添加一个 b 符号，你也会添加一个 a 符号。

这可以通过以下方式完成:

   S --> aSb 

但这是不完整的，因为我们需要一个规则来生成额外的 a s:

   A --> aA | a

将两个产生式规则组合成一个语法 CFG。

   S --> aSb | A
   A --> aA  | a

因此，您可以生成由 a 以及 a 和 b 和 ^ 模式组成的任何字符串。507 am

但是在上面的语法中有 没有 方法来生成 ^ 字符串。

所以，像这样改变这个语法:

   S --> B   | ^
   B --> aBb | A
   A --> aA  | a

这个语法可以生成 {am bn | m >= n} 语言。

注意 :为了生成 S--> B | ^ 空字符串，我通过添加 ^ 在语法中添加了额外的第一步，因此您可以添加 a 或您的符号字符串 b _0x70x70x70407040707070707067067690 (现在 B 扮演之前语法中的 S 的角色，生成相等数量的 a 和 b )

编辑: 感谢@Andy Hayden
您还可以为相同的语言编写等效的语法 {am bn | m >= n}:

   S --> aSb | A
   A --> aA | ^

注意:这里 A --> aA | ^ 可以生成零个或任意数量的 a 。这应该比我的语法更可取，因为它为相同的字符串生成一个较小的解析树。
(由于有效解析，高度更小更可取)

以下 提示 可能有助于为正式语言编写语法:

• You are to be clear about language that what it describes (meaning/pattern).
• You can remember solutions for some basic problems(the idea being that you can write new grammars).
• You can write rules for fundamental languages like I have written for RE in this example to write Right-Linear-Grammmar. The rules will help you to write Grammar for New Languages.
• One different approach is to first draw automata, then convert automata to Grammar. We have predefined techniques to write grammar from automata from any class of formal language.
• Like a Good Programmer who learns by reading the code of others, similarly one can learn to write grammars for formal languages.

另外你写的语法是错误的。