この言語は定期的かどうか？

Question

私は言語{4 ^（w∈G）34 ^（g）|アルファベット{0,1}の上にw、gānat}を持っています。

この言語が認識可能、決定可能、コンテキストフリー、定期的、またはこれらのどれでも認識可能であるかどうかを調べる必要があります。

それをやっているか知っているのでしょうか？

ありがとう

Answer 1

フォーム4^a 3 4^bの文字列を考えます。 w, gのa, bを見つけることができますか？まあ、gがbに等しくなければならず、それからw = a + gを選択できます。 a、bおよびgは自然数であるため、wでなければなりません。答えは、4^a 3 4^bの形式の任意の文字列に対して、あなたの言語に文字列を持ちます。

フォーム4^a 3 4^bのすべての文字列の言語は、正規表現4* 3 4*によって記述され、そのようにあなたの言語は定期的、文脈自由、決定可能で認識可能です。

あなたの言語が定期的ではなかったとします。どのようにあなたは言うことができますか？言語を想定して矛盾を引き出すために、正規言語のためにMyHill-Nerode TheoremまたはPumping Lemmaを使用することができます。

あなたの言語がコンテキストフリーではなかったとします。言語を想定していると仮定して矛盾を派生させるために、コンテキストフリー言語のためにポンピングリンマを使用することができます。

もちろん、あなたの言語が決められていないか認識可能であれば、あなたはさまざまな方法でそれを証明することができます。