0

DFA の問題 : L の完全な文法を書き、四重項と生成規則を含めます。

L ={x: ∃y ∈ {a, b}* : x = ay}

答え：

G={{S, A}, {a, b}, S, P}
P: S => aA
   A => aA | bA | λ

私の質問は:

  1. λforがあるのにforAがないのはなぜですか? λS
  2. 言語定義から、それは で始まり、aと のみを含むa任意の文字列ですがb、なぜ答えにA => bA. だとすると文字列が で始まるということでbはないA => bAですか？

どうもありがとう

4

1 に答える 1

1

1.λforがあるのにforAがないのはなぜですか? λS

λAnul は、感傷的な from を文に変換するためにfrom を派生させることができます。さらに、言語ステートメントによると、接頭辞の部分文字列y ∈ {a, b}* は nul (空の文字列) にすることができます。たとえば"a"、文字列は言語に属します。記号が含まれている場合y、言語の長さは複数になります。

Sλ空（またはヌル文字列と言う）は言語にないため、ヌルを導出しません。language の最小の文字列は single"a"です。

2.言語定義から、それは で始まり、aと のみを含むa任意の文字列ですがb、なぜ答えにA => bA. だとすると文字列が で始まるということでbはないA => bAですか？

start 変数から派生できる文字列のみSが language of grammar に含まれることに注意してください。A(開始変数ではない)から派生を開始することはできません。また、文字列から派生を開始するSと、常にaシンボルで始まります。

読むことをお勧めします: 「なぜターミナルが必要なのですか? 私のソリューションで十分ですか?」形式文法の基本的な定義について書いた場所。

于 2013-10-02T14:27:37.457 に答える