给定以下语言，构造语法{a ^ n b ^ m | n，m = 0,1,2，...，n< = 2m} [英] Construct grammar given the following language {a^n b^m | n,m = 0,1,2,...,n <= 2m}

问题描述

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

I just took my midterm but couldn't answer this question.

有人可以举几个例子，并为或
语言构造一个语法，至少告诉我如何我会去解决的吗？

Can someone please give a couple of examples of the language and construct a grammar for the language or at least show me how i will go about it?

也可以为 L 编写语法：

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

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

谢谢。

推荐答案

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

在阅读我的这篇文章之前答案，您应该先阅读： 用于创建无上下文语法的提示 。

您使用的语言是L = {a ⁿ b ^m | n，m = 0,1,2，...，n< = 2m}说明？

What is you language L = {aⁿ b^m | n,m = 0,1,2,..., n <= 2m } description?

语言说明：
语言 L 由所有包含符号 a 的字符串组成后跟符号 b ，其中符号 b 大于或等于 a 数量的一半。

Language description: The language L is consist of set of all strings in which symbols a followed by symbols b, where number of symbol b are more than or equals to half of number of a's.

要更清楚地理解：

以模式 a ⁿ b ^m ，先出现符号 a ，然后出现符号 b 。 a 的总数为 n 和 <$ c的数量$ c> b 是 m 。不等式说明了 n 和 m 之间的关系。要了解该方程式：

In pattern aⁿ b^m, first symbols a come then symbol b. total number of a 's is n and number of b's is m. The inequality equation says about relation between n and m. To understand the equation:

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 ）

numberOf(b) must be more then or equals to half of numberOf(a)

$ 一半 b
$ b

L中的一些示例字符串：

Some example strings in 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）。

So in language string any number of b are possible without a's. (any string of b) because any number is greater then zero (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 等于或等于 a 数量的一半em> 或更多（>）。

值得注意的一点是，总共 a 可以也要比 b 的数量多，但不能太多。而 b 的数量可以大于 a 的任意次数。

and interesting point to notice is that total a's can also be more then number of b's, but not too much. Whereas number of b's can be more then number of a's by any number of times.

另外两个重要的情况是：

Two more important case are:

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

• only a as a string not possible.

注意：由于 ^ 字符串也被允许，因为在 ^ ， numberOf（a）= numberOf（b）= 0 满足方程式。

note: null ^ string is also allowed because in ^ , numberOf(a) = numberOf(b) = 0 that satisfy equation.

_{一次，看来书写语法很困难，但实际上并不……}

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

According to language description, we need following kinds of rules:

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

 N --> ^  

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

rule 2: To generate any number of b

 B --> bB | b  

规则3 ：生成 a ：

（1）请记住，您生成的 a 而不生成 b 。

（2）因为 b 的数量大于= a 的一半；您需要为每个备用 a 生成一个 b

（3）不可能仅将 a 作为字符串，因此对于第一个（奇数）替代方案，您需要添加 b 和 a

（4） 可以丢弃以添加 b （但不是强制性的）

Rule 3: to generate a's:
(1) Remember you can't generate too many a's without generating b's.
(2) Because b's are more then = to half of a's; you need to generate one b for every alternate a
(3) Only a as a string not possible so for first (odd) alternative you need to add b with an a
(4) Whereas for even alternative you can discard to add b (but not compulsory)

因此，您整体语法：

   S --> ^ | A | B
   B --> bB | b

   A --> aCB | aAB | ^
   C --> aA | ^

此处 S 是开始变量。

在上述语法规则中，您可能对 A->银行| aAB | ^ ，因此以下是我的解释：

In the above grammar rules you may have confusion in A --> aCB | aAB | ^, so below is my explanation:

A --> aCB | aAB | ^   
       ^_____^
       for second alternative a 

C --> aA    <== to discard `b`    

and  aAB  to keep b

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

let us we generate some strings in language using this grammar rules, I am writing Left most derivation to avoid explanation.

  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 ⁵ b ² = aaaaabb 是 不可能。因为2> = 5/2 = 2.5 ==> 2> = 2.5不等式失败。因此我们也无法使用语法生成此字符串。我尝试在下面显示：

according to language a⁵ b² = aaaaabb is not possible. because 2 >= 5/2 = 2.5 ==> 2 >= 2.5 inequality fails. So we can't generate this string using grammar too. I try to show below:

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

In our grammar to generate extra a's we have to use C variable.

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 的规则，例如：

While my answer is done but I think you can change A's rules like:

A --> aCB | A | ^

尝试一下！

编辑：

_{就像@ us2012一样：在我看来，然后， S-> ^ | ab | aaSb | Sb 将是一个更简单的描述。我觉得这个问题对OP以及其他问题也都很好。}

_{as @us2012 commented: It would seem to me that then, S -> ^ | ab | aaSb | Sb would be a simpler description. I feel this question would be good for OP and other also.}

OP的语言：

L = {a ⁿ b ^m | n，m ＝ 0，1,2，...，n ＜＝ 2m}。

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

@ us2012的语法：

@us2012's Grammar:

S -> ^ | ab | aaSb | Sb    

@ us2012的问题：

@us2012's question:

这个语法是否还会产生语言L？

Whether this grammar also generates language L?

答案是是！

a 的数量= n 和的数量之间的语言不平等 b = m是 n =< 2m

我们也可以理解为：

 n =< 2m

 that is 

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

的两倍，在语法上，即使我们加上一个 或两个 a ，我们还添加了一个 b 。因此，最终 a 的数量不能超过 b 。

And In grammar, when even we add one or two a's we also add one b . So ultimately number of a can't be more then twice of number of b.

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

Grammar also have rules to generate. any numbers of b's and null ^ strings.

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

So the simplified Grammar provided by @us2012 is CORRECT and also generates language L exactly.

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

Notice: The first solution came from derivation as I written in am linked answer, I started with language description then tried to write some basic rules and progressively I could write complete grammar.

@ us2012的答案来自于aptitude，您可以通过阅读其他解决方案并为您编写相同的语法来获得编写语法的能力，就像学习编程一样。

Whereas @us2012 answer came by aptitude, you can gain the aptitude to write grammar by reading others solution and writing your for same..like you learn programming.

这篇关于给定以下语言，构造语法{a ^ n b ^ m | n，m = 0,1,2，...，n&lt; = 2m}的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！