は最大形式の公式言語を認識します

Question

現在、私は公式の言語と文法を学び、理解しようとしています。 私はチョムスキー階層を理解していますが、どのように解決策が得られたのか分かりません。 タスクは次のとおりです。

G=({S},{a,b},S,P) 
P={S->epsilon, S->aS, S->Sb} 

1. この文法の最大のタイプは何ですか？
2. L(G)の最大タイプは何ですか？

私は文法は2タイプであることを知っているが、答えにL(G)が タイプ3.

であることを書かれたことは、この言語を記述したタイプ3文法もあるようですが、どのようにあなたが正式な言語の最大のタイプはどれですか？いくつかのトリックはありますか？

Answer 1

私は、言語のどのクラスを常に指示するのが簡単でアルゴリズム的な方法はないと思います。L(G)です。私は、一般的には、一方的にしか証明できない場合があると思います。これは、無制限の文法が算術を符号化できることを考えると、不完全性/不定性から生じる。これは非常に手で波打っています。

ヒューリスティックには、あなたの言語が何であるかを理解しようとすることができます。文法をより簡単にするように変換できますが、これは成功を保証しません。

この特定のケースでは、言語が何であるか把握し、それが正規であることを認識し、そのための文法を書き留めるのはあまりにも悪くありません。

S -> e 
S -> aS 
S -> Sb 

Sに由来する任意の文字列は、S -> aSによってaの任意の数で開始することができ、そしてS -> Sbによってbの任意の数で終わることができます。 （1）L（G）がbのサブセットであり、（2）bがL（G）のサブセットであることを示すことによって証明することができる。

（1）証拠は、出願番号S -> aSおよびS -> Sbの誘導によるものです。基本ケース：これらのどちらも適用されない場合、文字列eのみが導出可能です。 eはa*b*であるので、ベースケースが確認されます。誘導仮説：kまでのS -> aSおよびS -> Sbのアプリケーションがa*b*にあると仮定します。誘導ステップ：これらのプロダクションのk+1アプリケーションを使用して派生した文字列もa*b*にあることを示します。 k+1の作品で派生した文字列には、k+1の作品をスキップしてkの作品で派生した文字列があります。これは、プロダクションが非終端セットを同じに保つためです。我々はすでにkで得られたこの短い文字列がa*b*にあることを知っています。私たちは、考慮すべき2つのケースがあります。

1. S -> aS：これはa*b*でそれを維持、a*b*で短い文字列の前に1 aを追加します。
2. S -> Sb：これは、短い文字列の末尾にを追加し、a*b*のままにします。

両方のケースがa*b*内の文字列を保持しているので、制作のk+1用途に派生したすべての文字列がa*b*であると、誘導により、文法によって生成されたすべての文字列があります。

（2）a^n b^mの文字列をa*b*とします。これは、文法によって次のように生成される。A -> aS,mB -> Sbのアプリケーション、およびS -> eのアプリケーション。したがって、a*b*のすべての文字列が文法によって生成されます。