これらの証明方法は正規の言語です

Question

私は援助が必要なこれらの質問があります。私はそれらが正規の言語であることを証明しなければなりません。私は質問3と4でDSQまたはDFがどのようになっているのか分かりません。私は "SpiserによるComp理論へのイントロ"という本を持っていますが、DSQまたはDFに言及しているものは見つかりませんでした。

1）L = {W .... W∈Σ*}Σ= {A、B}

2）Trancate（N）= {WA^NW∈Σ*∈Σ| W | = N}

3）DSQ = {^ P、B^P：Pの素数}

4）DF = {A^NB^N：N> 0以上}

Answer 1

すべての4つのこれらの言語の中では定期的ではありません。言語が規則的でないことを証明するために使用できるさまざまな手法がいくつかあります。サンプルは次のとおりです。

1. pumping lemma for regular languagesを使用してください。これは、言語が規則的でないことを証明する最も広く教えられている技法です。あなたが転がっSipserのコピーを持っていることを述べ、彼は第1章で

2. Myhill-Nerode theoremを使用し、被写体の良い治療を提供します。この強力な定理は、あなたの頭を包み込むためのポンピング補題よりもややこしいですが、言語を証明するためのツールとしての二重義務は、あなたが非正規言語を嗅ぐために使うことができる優れた直感を提供します。 （これは私のCS理論の紹介で私の生徒に教えるテクニックです）。リンクされたスライドには、{a ⁿ b ⁿ | N in N}は、最初の原則からも、Myhill-Nerodeを使っても、規則的ではありません。

3. closure properties of regular languagesを使用してください。通常の言語を標準言語にマッピングする特定の操作を適用した後に、正規言語で終わることを証明することによって、言語が正規でないことを示すことができます。あなたが提供してきた例を見ている

、私は（1）非正規であるポンプの補題は、その言語を証明するための最も簡単なルートになると思います。 Myhill-Nerode定理は、（3）と（4）の簡単な作業をすべきである。 （2）、あなたは言語の交差点を取って検討する必要がありますについてはaとb ^☆☆ B ^☆、その結果の言語にMyhill-Nerodeさんやポンプの補題を適用します。