使用以下语言构造语法{a ^ nb ^ m | n,m = 0,1,2,...,n <= 2m}

Question

我刚接受了期中考试,但无法回答这个问题.

有人可以给出一些语言的例子,并为语言构建一个语法,或者 至少告诉我如何去做它？

另外如何编写语法L:

L = {a ⁿ b ^m | n,m = 0,1,2,...,n <= 2m}？

提前致谢.

Answer 1

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

在阅读我的回答之前,您应该先阅读:创建无上下文语法的提示.

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

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

语言描述:语言大号是由组,其中所有的符号串的 a随后的符号b,其中符号的数目b 是大于或等于一半的数量的a的.

要更清楚地理解:

在模式a ⁿ b ^m中,第一个符号a然后是符号b.a's的总数和's的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的(一)

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 

所以在语言字符串中,任何数量的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

• 有趣的是要注意的是,总数a还可以超过数量b,但不能太多.而数量的数量b可以是a任意次数的数量.

另外两个重要案例是:

• 只a作为字符串不可能.

• 注意:^也允许使用null 字符串,因为in ^,numberOf(a) = numberOf(b) = 0即满足等式.

_{一下子,看起来编写语法很难,但实际上并非......}

根据语言描述,我们需要遵循以下规则:

规则1:生成^空字符串.

 N --> ^  

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

 B --> bB | b  

规则3:产生a的:
(1)请记住,你不能产生太多a",而不会产生小号b的.
(2)因为b它们超过了一半a; 你需要b为每个替代品生成一个 (3)只作为一个不可能的字符串,所以对于第一个(奇数)替代品你需要添加一个 (4)而对于偶数替代你可以丢弃添加(但不是必须的) a
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

还有一个非成员字符串:

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

在我们的语法中生成额外的a's我们必须使用C变量.

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

虽然我的答案已经完成,但我认为你可以改变以下A规则:

A --> aCB | A | ^

试试看!!

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

OP的语言:

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

@ us2012的语法:

S -> ^ | ab | aaSb | Sb    

@ us2012的问题:

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

答案是肯定的!

a's =的n 数量与b= m的数量之间的语言不等式是n =< 2m

我们也可以理解为:

 n =< 2m

 that is 

 numberOf(a) = <  twice of numberOf(b) 

并在语法的时候,连我们添加一个或2 a的还要增加一个 b.所以最终的数量a不能超过数量的两倍b.

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

因此@ us2012提供的简化语法是正确的,并且还完全生成语言L.

注意: 第一个解决方案来自派生,因为我写的是链接的答案,我从语言描述开始,然后尝试编写一些基本规则,并逐步编写完整的语法.

虽然@ us2012的答案来自aptitude,但你可以通过阅读别人的解决方案和写你的语言来获得编写语法的能力.就像你学习编程一样.