14

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

例如

L = {am bn | m >= n}

我得到的是：

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

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

4

4 回答 4

57

如何用示例 a m b n编写 CFG

L = {a m b n | m >= n}。

语言描述： a m b n由a后跟b其中 number ofa等于或大于 number of 组成b。

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

所以总是有一对一a的，b但额外a 的也是可能的。感染字符串只能包含a。还要注意^null 是语言的成员，因为在^ NumberOf(a) = NumberOf(b) = 0

如何编写一个接受由字符串 a m b n形成的语言的语法？

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

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

   S --> aSb

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

   A --> aA | a

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

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

因此，您可以生成由aalsoa和bin (a m b n ) 模式组成的任何字符串。

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

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

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

该文法可以生成 {a m b n | m >= n} 语言。

注意：要生成^空字符串，我在语法中添加了一个额外的第一步S--> B | ^，因此您可以添加^符号a和字符串b。（现在B扮演S从以前的语法生成相等数量的a和b的角色）

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

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

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

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

  • 你要清楚它所描述的语言（含义/模式）。
  • 您可以记住一些基本问题的解决方案（您可以编写新语法的想法）。
  • 您可以为基本语言编写规则，就像我在这个示例中为 RE 编写的那样编写 Right-Linear-Grammmar。这些规则将帮助您编写新语言语法。
  • 一种不同的方法是首先绘制自动机，然后将自动机转换为语法。我们有预定义的技术，可以从任何类型的形式语言的自动机编写语法。
  • 就像一个优秀的程序员通过阅读别人的代码来学习一样，同样地，一个人也可以学习为形式语言编写语法。

你写的语法也是错误的。

于 2013-02-28T08:06:33.467 回答
5

您想为以下语言创建语法

    L= {an bm | m>=n }

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

这是该语言的语法

      S-> aSb | Sb | b | ab

在这个语法中，每个“a”都有一个“b”。但是可以在不生成任何“a”的情况下生成 b。

您还可以尝试以下语言：

           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
于 2015-03-26T15:53:39.190 回答
3

最小变量：S -> a S b | 一个 S | e

于 2015-02-18T18:00:19.010 回答
0

变量更少：

S -> a S b | 一个 S | ab | e

于 2014-04-06T21:12:31.783 回答