automation - これらの言語がどのクラスに属しているかを判断するにはどうすればよいですか？

Question

{WW}-決定可能だが文脈自由ではない
{WW^R}-文脈自由だが正規言語ではない
Σ*-正規言語
どのクラスに属しているかをどのように判断できますか？

Answer 1

私の答えがあなたに役立つかもしれません：

L ₁ = {ww | w∈{a、b} ^* }

（プッシュダウンオートマトン）PDAは不可能であるため（非決定性PDAでさえ）、文脈自由言語ではありません。なんで？wスタックの最初にプッシュするとします。w2番目と1番目を一致させるには、最初を逆の順序でwプッシュする必要があります（スタックの内容と2番目を逆の順序で一致させる必要があります）。これはスタックでは不可能です（入力を逆の順序で読み取ることはできません）。有限のステップ数の後に常に半分に なるL1のaを_描画できるため、決定可能ですが。wwTuring Machine

L ₃ = {ww ^R | w∈{a、b} ^* }

言語L3_{は、可能であるが有限自動化がL 3で}n-PDA不可能であるため、非決定性文脈自由言語です。正規言語の反復補題を使用してこれを証明することもできます。

Σ*-正規言語（RL）

Σ*は正規表現（RE）です。たとえば、Σ = {a, b} then RE is (a + b)* REがRLに対してのみ可能である場合。

私の質問の例はあなたにとってもっと役立つかもしれません。