2

中間試験を受けたばかりですが、この質問に答えることができませんでした。

誰かが言語の例をいくつか挙げて、その言語の文法を構築するか 、少なくとも私がそれをどのように行うかを教えてもらえますか?

また、 の文法の書き方L:

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

前もって感謝します。

4

1 に答える 1

8

形式言語の文法の書き方は？

私のこの回答を読む前に、最初に読む必要があります: Tips for creating Context free grammars。

{a n b m |の文法 n、m = 0、1、2、...、n <= 2m}

あなたの言語は何ですか L = {a n b m | n,m = 0,1,2,..., n <= 2m } 説明?

言語の説明: 言語Laは、シンボル の後にシンボル が続くすべての文字列のセットで構成さ れますb。ここで、シンボルの数は の数の半分b 以上です。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

したがって、言語文字列では、bがなくてもいくつでも可能aです。(b の任意の文字列) 任意の数値が 0 より大きいため (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

  • 注目すべき興味深い点は、 totalaは number よりも大きくなる可能性がありますがb、多すぎないことです。一方、 の数は、bの数よりも何回でも多くなる可能性がありますa。

さらに重要な 2 つのケースは次のとおりです。

  • 文字列としてのみa使用できません。

  • 注:で式を満たすため、null^文字列も許可されます。^numberOf(a) = numberOf(b) = 0

文法を書くのは一見難しそうに見えますが、実際にはそうではありません...

言語記述によると、次の種類の規則が必要です。

ルール 1 :^空文字列を生成する。

 N --> ^

ルール 2 : 任意の数を生成するb

 B --> bB | b

ルール 3 : を生成するにはa: (1) を生成せずに
を生成しすぎることはできないことに注意してください。 (2) 's は 's の半分よりも大きいので = 's; すべての代替に対して1つ生成する必要があります （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

非メンバー文字列の場合はもう 1 つ:

言語によると、a 5 b 2 =aaaaabbは不可能です。2 >= 5/2 = 2.5 ==> 2 >= 2.5 不等式は失敗するためです。したがって、文法を使用してもこの文字列を生成することはできません。以下に示してみます。

extra を生成する文法で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私の答えは完了していますが、のルールを次のように変更できると思います。

A --> aCB | A | ^

試してみる！！

EDIT：
@ 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 を生成するかどうか?

答えはイエスです！

aの数=n と= の数bmの間の言語における不等式は、n =< 2m

次のようにも理解できます。

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

また、文法では、 を1 つまたは2 つ追加すると、 も 1 つa追加されます。したがって、最終的に number ofは number of の 2 倍を超えることはできません。 bab

文法には、生成する規則もあります。bとヌル文字列の任意の数^。

したがって、@us2012 によって提供された簡略化された文法は正しく、言語 L も正確に生成します。

注意： 最初の解決策は、私がリンクされた回答で書いたように、派生から生まれました。言語の説明から始めて、いくつかの基本的なルールを書き込もうとし、徐々に完全な文法を書くことができました。

@us2012 の答えは適性によるものでしたが、プログラミングを学ぶのと同じように、他の人のソリューションを読んだり、独自のソリューションを書いたりすることで、文法を書く適性を得ることができます。

于 2013-03-22T19:44:09.357 に答える