14

私は CFG を初めて使用し
ます。言語を生成する CFG を作成する際のヒントを教えてください。

例えば

L = {am bn | m >= n}

私が得たものは次のとおりです。

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

bしかし、 の数が の数よりも多くなる可能性があるため、この領域は間違っていると思いますa。

4

4 に答える 4

57

例 a m b nを使用した CFG の記述方法

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

言語の説明: a m b nは、 の数が の数と等しいかそれ以上aである で構成されます。bab

文字列の例:{^, a, aa, aab, aabb, aaaab, ab......}

したがって、常に 1a対 1 ですbが、追加a も可能です。感染文字列はaのみで構成できます。^また、null は language のメンバーであることにも注意してください。^ NumberOf(a) = NumberOf(b) = 0

文字列 a m b nによって形成される言語を受け入れる文法を作成する方法は?

文法では、記号を追加するとb記号も追加するという規則が必要ですa。

そして、これは次のようなもので行うことができます:

   S --> aSb

aしかし、余分なs を生成するルールが必要なため、これは不完全です。

   A --> aA | a

2 つのプロダクション ルールを 1 つの文法CFG に結合します。 

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

aしたがって、 alsoaおよびbin (a m b n ) パターンで構成される任意の文字列を生成できます。

しかし、上記の文法では文字列を生成する方法がありません^。

したがって、この文法を次のように変更します。

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

この文法は {a m b n | m >= n} 言語。

注: null 文字列を生成するため^に、 を追加して文法の最初のステップを追加しS--> B | ^ました。(は以前の文法からの役割を果たし、同数の と を生成するようになりました) ^abBSab

編集： @Andy Haydenのおかげ
で、同じ言語の同等の文法を書くこともできます {a m b n | m >= n}: 

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

注意: ここでA --> aA | ^は、ゼロまたは任意の数のa. そして、同じ文字列に対してより小さな解析ツリーを生成するため、それは私の文法よりも好ましいはずです。
(効率的な解析のため、高さが小さい方が望ましい)

次のヒントは、正式な言語の文法を書くのに役立つ場合があります。

  • 言語について、それが何を表しているか (意味/パターン) を明確にする必要があります。
  • いくつかの基本的な問題の解決策を覚えることができます (新しい文法を書くことができるという考えです)。
  • この例で RE について書いたように、基本言語のルールを記述して Right-Linear-Grammmar を記述できます。ルールは、新しい言語の文法を書くのに役立ちます。
  • 別のアプローチの 1 つは、最初にautomataを描画し、次に automata を Grammar に変換することです。形式言語の任意のクラスのオートマトンから文法を記述するための事前定義された手法があります。
  • 他人のコードを読んで学ぶ優れたプログラマーのように、形式言語の文法を書くことを学ぶことができます。

また、あなたが書いた文法は間違っています。

于 2013-02-28T08:06:33.467 に答える
5

次の言語の文法を作成したい

    L= {an bm | m>=n }

これは、「b」の数が「a」の数よりも大きいか等しい必要があることを意味します。または、各「b」に対して最大で 1 つの「a」が存在する可能性があると言えます。他の方法ではありません。

ここにこの言語の文法があります

      S-> aSb | Sb | b | ab

この文法では、各 'a' に対して 1 つの '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 に答える