grammar - 左線形および右線形の文法

Question

以下の言語の左線形および右線形の文法を構築するのに助けが必要ですか？

a)  (0+1)*00(0+1)*
b)  0*(1(0+1))*
c)  (((01+10)*11)*00)*

a）私は以下を持っています：

Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

これは正しいです？b＆cのサポートが必要です。

Answer 1

正規表現から同等の正規文法を構築する

まず、正規表現（RE）から正規文法（RG）を作成するための簡単なルールから始めます。
私は右線形文法のルールを書いています（左線形文法の同様のルールを書くための練習問題として残しています）

注：大文字は変数に使用され、小文字は文法の終端に使用されます。NULL記号は^。「任意の数」という用語は、*スターク​​ロージャである0回以上を意味します。

[基本的なアイデア]

• SINGLE TERMINAL： REが単純な場合、1つのプロダクションルール（ここで）のみを使用して、と同等のRG e (e being any terminal)を記述できます。GS --> eS is the start symbol

• UNION OPERATION： REがの形式e + fである場合、両方とも、 2つの生成ルールでe and f are terminals書くことができます 。これは同等のRGです。 GS --> e | f

• 連結： REがの形式efである場合、両方とも、 2つの生成ルールe and f are terminalsを使用して書くことができます 。これは同等のRGです。 GS --> eA, A --> f

• STAR CLOSURE： REの形式e*が、wheree is a terminalおよび* Kleene star closureoperationの場合、2つのプロダクションルールを、、で記述できますG。S --> eS | ^これは同等のRGです。

• PLUS CLOSURE： REがe ⁺の形式である場合、ここでe is a terminal、+ Kleene plus closure操作の場合、2つのプロダクションルールを、、で記述できますG。S --> eS | eこれは同等のRGです。

• UNIONのSTARCLOSURE： REが（e + f）*の形式である場合、両方ともe and f are terminals、、で3つの生成ルールを記述できますG。S --> eS | fS | ^これは同等のRGです。

• ユニオンのプラスクロージャ： REが（e + f）⁺の形式である場合、両方ともe and f are terminals、、で4つの生成ルールを記述できますG。S --> eS | fS | e | fこれは同等のRGです。

• 連結のスタークロージャ： REが（ef）*の形式である場合、両方とも、、でe and f are terminals3つの生成ルールを記述できますG。S --> eA | ^, A --> fSこれは同等のRGです。

• 連結に関するプラス の閉鎖：REが（ef）⁺の形式である場合、両方とも、、e and f are terminalsで3つの生成ルールを記述できますG。S --> eA, A --> fS | fこれは同等のRGです。

上記のすべてのルールを理解していることを確認してください。要約表は次のとおりです。

+-------------------------------+--------------------+------------------------+
| TYPE                          | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR   |
+-------------------------------+--------------------+------------------------+
| SINGLE TERMINAL               | e                  | S --> e                |
| UNION OPERATION               | e + f              | S --> e | f            |
| CONCATENATION                 | ef                 | S --> eA, A --> f      |
| STAR CLOSURE                  | e*                 | S --> eS | ^           |
| PLUS CLOSURE                  | e+                 | S --> eS | e           |
| STAR CLOSURE ON UNION         | (e + f)*           | S --> eS | fS | ^      |
| PLUS CLOSURE ON UNION         | (e + f)+           | S --> eS | fS | e | f  |
| STAR CLOSURE ON CONCATENATION | (ef)*              | S --> eA | ^, A --> fS |
| PLUS CLOSURE ON CONCATENATION | (ef)+              | S --> eA, A --> fS | f |
+-------------------------------+--------------------+------------------------+

注：記号は端子でeありf、^はNULL記号でありS、開始変数です。

[答え]

今、私たちはあなたの問題に来ることができます。

a） (0+1)*00(0+1)*

言語の説明：すべての文字列は0と1で構成され、少なくとも1組の。が含まれ00ます。

• 右線形文法：

  S-> 0S | 1S | 00A
  A-> 0A | 1A | ^

  文字列は、0sと1sの任意の文字列で開始できます。そのため、ルールが含まれています。s --> 0S | 1S少なくとも1つのペアであるため、00null記号はありません。S --> 00Aが含まれているのは、の後0に1できるから00です。記号Aは、。の後の0と1を処理し00ます。

• 左線形文法：

  S-> S0 | S1 | A00
  A-> A0 | A1 | ^

b） 0*(1(0+1))*

言語の説明：任意の数の0、続いて任意の数の10と11。
{1（0 + 1）= 10+11であるため}

• 右線形文法：

  S-> 0S | A | ^
  A-> 1B
  B-> 0A | 1A | 0 | 1

  文字列は任意の数で始まる0ため、ルールS --> 0S | ^が含まれ、次に、を使用して生成10および11任意の回数のルールが含まれA --> 1B and B --> 0A | 1A | 0 | 1ます。

  他のオルタナ右翼の文法は

  S-> 0S | A | ^
  A-> 10A | 11A | 10 | 11

• 左線形文法：

  S-> A | ^
  A-> A10 | A11 | B
  B-> B0 | 0

  別の形式は

  S-> S10 | S11 | B | ^
  B-> B0 | 0

c） (((01+10)*11)*00)*

言語の説明：最初は、（）内に存在するすべてのものの外側に*（星）があるため、言語にはnull（^）文字列が含まれています。また、言語の文字列がnullでなく、00で終わる場合もあります。この正規表現は（（（A）* B）* C）*の形式で簡単に考えることができます。ここで、（A）*は（01 + 10）です。 *これは01と10の任意の数の繰り返しです。文字列にAのインスタンスがある場合、（A）* BとBは11であるため、Bは反抗的になります。
いくつかの例の文字列{^、00、0000、000000、 1100、111100、1100111100、011100、101100、01110000、01101100、0101011010101100、101001110001101100 ....}

• 左線形文法：

  S-> A00 | ^
  A-> B11 | S
  B-> B01 | B10 | A

  S --> A00 | ^文字列はnullであるか、nullでない場合は、で終わるため00です。文字列が。で終わる場合00、変数Aはパターンと一致します((01 + 10)* + 11)*。この場合も、このパターンはnullにするか、で終わる必要があります11。nullの場合、Aそれを再度照合します。Sつまり、文字列は。のようなパターンで終わります(00)*。パターンがnullでない場合は、とB一致し(01 + 10)*ます。B可能な限り一致するAと、文字列の一致を再開します。これにより、最も外側の*inが閉じられ((01 + 10)* + 11)*ます。

• 右線形文法：

  S-> A | 00S | ^
  A-> 01A | 10A | 11S

あなたの質問の2番目の部分：

For a) I have the following:
Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

（答え）
あなたの解決策は次の理由で間違っています、

文字列を生成できないため、左線形文法が間違ってい0010 ます。1000文字列を生成できないため、右線形文法が間違って います。どちらも質問（a）の正規表現によって生成された言語ですが。

編集
正規表現ごとにDFAを追加します。それが役立つと思うように。

a） (0+1)*00(0+1)*

b） 0*(1(0+1))*

c） (((01+10)*11)*00)*

この正規表現のDFAを描画するのは、巧妙で複雑です。
_{このために、DFAを追加したかった}

(((01+10)*11)*00)* タスクを単純化するために、私にとってREの親切な形成はREが次のように見えると考える必要があります(a*b)*

(((01+10)*11)* 00 )*
(          a*   b )*

実際、上記の表現では、それはaその形で自己(a*b)* です((01+10)*11)*

RE(a*b)*はに等しい(a + b)*b + ^。（a b）のDFAは次のとおりです。

のDFA((01+10)*11)*は次のとおりです。

のDFA(((01+10)*11)* 00 )*は次のとおりです。

_{上記の3つのDFAの構築に類似性を見つけてください。あなたが最初のものを理解するまで先に進まないでください}

Answer 2

正規表現を左または右の線形正規文法に変換するための規則