2

我刚参加了期中考试，但无法回答这个问题。

有人可以举几个该语言的例子并为该语言构建一个语法，或者 至少告诉我我将如何去做？

还有如何写语法L：

L = {a n b m | n,m = 0,1,2,..., n <= 2m } ?

提前致谢。

4

1 回答 1

8

如何为形式语言编写语法？

在阅读我的这个答案之前，您应该先阅读：创建上下文无关语法的技巧。

{a n b m |语法 n,m = 0,1,2,..., n <= 2m }

你是什​​么语言 L = {a n b m | n,m = 0,1,2,..., n <= 2m } 描述？

语言描述：语言L由所有字符串的集合组成，其中符号 a后跟符号b，其中符号b 的数量大于或等于's的数量的一半。a

为了更清楚地理解：

在模式a n b m中，首先是符号a，然后是符号b。的总数a是n和的数量b是 m。不等式表示 和 之间的n关系m。要理解等式：

given:   n <= 2m   
=>       n/2 <= m       means `m` should be = or > then n/2

=>       numberOf(b) >= numberOf(a)/2    ...eq-1

所以n和m的不等式说：

numberOf( b ) 必须大于或等于numberOf ( a )的一半

L 中的一些示例字符串：

b   numberOf(a)=0 and numberOf(b)=1  this satisfy eq-1        
bb  numberOf(a)=0 and numberOf(b)=2  this satisfy eq-1

因此，在语言字符串中，没有's 的任何数量b都是可能的。a(b 的任何字符串) 因为任何数字都大于零 (0/2 = 0)。

其他示例：

                                     m   n
                                 --------------  
ab     numberOf(a)=1 and numberOf(b)=1 > 1/2   
abb    numberOf(a)=1 and numberOf(b)=2 > 1/2  
abbb   numberOf(a)=1 and numberOf(b)=3 > 1/2  
aabb   numberOf(a)=2 and numberOf(b)=2 > 2/2 = 1  
aaabb  numberOf(a)=3 and numberOf(b)=2 > 3/2 = 1.5
aaaabb numberOf(a)=4 and numberOf(b)=2 = 4/2 = 2

注意事项：

  • 以上所有字符串都是可能的，因为b's 的数量等于（=）或更多（>）数量的一半。a

  • 有趣的一点是，totala也可以超过 number of b，但不能太多。而b's 的数量可以比a's 的数量多任意次数。

两个更重要的案例是：

  • 仅a作为字符串是不可能的。

  • 注意：空^字符串也是允许的，因为在 中^，numberOf(a) = numberOf(b) = 0满足等式。

乍一看，写语法很难，但实际上并不...

根据语言描述，我们需要以下几种规则：

规则 1：生成^空字符串。

 N --> ^

规则 2：生成任意数量的b

 B --> bB | b

规则 3：生成a's： (1) 请记住，如果不生成's
，就不能生成太多's。 (2) 因为's 多于 = 到's 的一半；您需要为每个备用生成一个 （3）仅作为字符串不可能，因此对于第一个（奇数）替代您需要添加一个 （4）而对于甚至替代您可以丢弃添加（但不是强制性的）ab
baba
aba
b

所以你的整体语法：

   S --> ^ | A | B
   B --> bB | b
   
   A --> aCB | aAB | ^
   C --> aA | ^

这S是开始变量。

在上面的语法规则中，你可能会有混淆A --> aCB | aAB | ^，下面是我的解释：

A --> aCB | aAB | ^   
       ^_____^
       for second alternative a 
        
C --> aA    <== to discard `b`    

and  aAB  to keep b

让我们使用这个语法规则生成一些语言中的字符串，我正在写最左派生以避免解释。

  ab     S --> A --> aCB --> aB --> ab                        
  abb    S --> A --> aCB --> aB --> abB --> abb
  abbb   S --> A --> aCB --> aB --> abB --> abB --> abbB --> abbb 
  aabb   S --> A --> aAB --> aaABB --> aaBB --> aabB --> aabb
  aaabb  S --> A --> aCB --> aaAB -->  aaaABB --> aaaBB --> aaabB --> aaabb
  aaaabb S --> A --> aCB --> aaAB --> aaaCBB --> aaaaABB --> aaaaBB 
                                                         --> aaaabB 
                                                         --> aaaabb

非成员字符串的另一个：

根据语言 a 5 b 2 =aaaaabb是不可能的。因为 2 >= 5/2 = 2.5 ==> 2 >= 2.5 不等式失败。所以我们也不能使用语法生成这个字符串。我尝试在下面显示：

在我们的语法中生成额外a的，我们必须使用 C 变量。

S --> A 
  --> aCB 
  --> aaAB 
  --> aa aCB B 
  --> aaa aA BB 
  --> aaaa aCB BB  
           ---              
            ^
           here with first `a` I have to put a `b` too

虽然我的回答已经完成，但我认为您可以更改A's 规则，例如：

A --> aCB | A | ^

试试看！！

编辑：
正如@us2012 评论的那样：在我看来，那S -> ^ | ab | aaSb | Sb将是一个更简单的描述。我觉得这个问题对 OP 和其他也有好处。

OP的语言：

L = {a n b m | n,m = 0,1,2,..., n <= 2m}。

@us2012 的语法：

S -> ^ | ab | aaSb | Sb

@us2012 的问题：

这个文法是否也生成语言 L？

答案是肯定的！

anumber of 's =n 和 number of b= m之间的语言不等式是n =< 2m

我们也可以理解为：

 n =< 2m
 
 that is 
 
 numberOf(a) = <  twice of numberOf(b)

而在语法中，即使我们添加一两个 's ，a我们也会添加一个 b。所以最终数量a不能超过数量的两倍b。

语法也有规则要生成。任意数量的b' 和空^字符串。

因此@us2012 提供的简化语法是正确的，并且也准确地生成了语言 L。

注意： 第一个解决方案来自推导，因为我写的是链接答案，我从语言描述开始，然后尝试编写一些基本规则，逐步我可以编写完整的语法。

而@us2012 的答案来自 aptitude，您可以通过阅读其他人的解决方案并为某些人编写自己的解决方案来获得编写语法的能力 - 就像您学习编程的方式一样。

于 2013-03-22T19:44:09.357 回答