创建"Context Free Grammar"的提示

Question

我是CFG的新手,
有人可以给我一些关于创建生成某种语言的CFG的技巧

例如

L = {am bn | m >= n}

我得到的是:

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

但是我认为这个领域是错误的,因为有可能的数量b可能大于a.

Answer 1

如何使用示例a ^m b ⁿ编写CFG

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

语言描述: a ^m b ⁿ由a后面跟着的b数字a等于或等于数字b.

一些示例字符串: {^, a, aa, aab, aabb, aaaab, ab......}

因此,总有一对一a,b但额外a 是可能的.感染字符串只能由a.另请注意,^null是语言的成员,因为在^ NumberOf(a) = NumberOf(b) = 0

如何编写接受字符串a ^m b ⁿ形成的语言的语法？

在语法中,应该有规则,如果你添加一个b符号,你也添加一个a符号.

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

   S --> aSb 

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

   A --> aA | a

将两个生产规则合并为一个语法CFG.

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

所以,你可以生成包含任何字符串a也a和b在(一^米 b ^ñ)模式.

但在上面的语法中,没有办法生成^字符串.

所以,改变这个语法是这样的:

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

这个语法可以生成{a ^m b ⁿ | m> = n}语言.

注意:要生成^空字符串,我在语法中添加了额外的第一步S--> B | ^,因此您可以添加^或者您的符号字符串a和b.(现在B扮演S以前语法的角色来生成相同数量的a和b)

编辑:感谢@Andy Hayden
您也可以为同一种语言编写等效语法{a ^m b ⁿ | m> = n}:

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

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

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

• 你应该清楚它所描述的语言(意义/模式).
• 您可以记住一些基本问题的解决方案(想法是您可以编写新的语法).
• 您可以编写基本语言的规则,例如我在本例中为RE编写的Right-Linear-Grammmar.规则将帮助您为新语言编写语法.
• 一种不同的方法是首先绘制自动机,然后将自动机转换为语法.我们有预定义的技术从任何一种形式语言的自动机编写语法.
• 就像一个通过阅读他人代码来学习的优秀程序员一样,同样可以学习为正式语言编写语法.

_{你写的语法也是错的.}

Answer 2

您想为以下语言创建语法

    L= {an bm | m>=n }

这意味着“ b”的数量应大于或等于“ a”的数量，或者您可以说每个“ b”最多可以有一个“ a”。没有其他方法。

这是这种语言的语法

      S-> aSb | Sb | b | ab

在此语法中，每个“ a”都有一个“ b”。但是可以生成b而不会生成任何“ a”。

您还可以尝试以下语言：

           L1= {an bm | m > n }
           L2= {an bm | m >= 2n }
           L3= {an bm | 2m >= n }
           L4= {an bm | m != n }

我正在为每种语言提供语法。

对于L1

         S-> aSb | Sb | b

对于L2

         S-> aSbb | Sb | abb

对于L3

         S-> AASb | Sb | aab | ab | b

对于L4

        S-> S1 | S2
        S1-> aS1b | S1b | b
        S2-> aS2b | aS2 | a