1

私は現在、オートマトンの理論のコースを受講していますが、次の問題が発生しました。私は1番目の質問の答えを思いつきましたが、2番目の質問のステートメントについて混乱しました.

(i) S = {aa,b} である言語 S* の再帰的定義を与えます。

ステップ 1: Lamba、aa、b は S にあります。

ステップ 2: x が S にある場合、bx と xb も S にある。

私は私の答えを確認したいです。

そして、次の質問は私が完全に混乱しており、答えを出すことができません。

(ii) T = {w1, w2, w3, w4} という言語 T* の再帰的な定義を与えてください。ここで、これらの w は特定の単語です。

4

1 に答える 1

0

(i) 非常に近い。少なくとも 1 つのルールが欠落しており、不要なルールが 1 つあります。xaaステップ 2 でまたはのいずれかが必要ですaax。ステップ 2 で指定したルールの 1 つだけが必要であり、両方は必要ありません。そうでなければ、これは正しいです。最小限の再帰的な定義は次のとおりです。

  1. ラムダは S
  2. x が S にある場合、aax と bx は S にあります。

(ii) (i) と同じですが、一般化されています。答えは

  1. ラムダは T
  2. x が T にある場合、w1x、w2x、w3x、w4x は T にあります。
于 2015-08-26T20:56:08.623 に答える