regular-language - この言語は規則的ですか?

Question

私は言語 {4^(w⋅g)34^(g)|w,g∈NAT} をアルファベット {0,1} で持っています。

この言語が認識可能か、決定可能か、文脈自由か、規則的か、またはこれらのいずれでもないかを調べる必要があります。

どうすればそれを行うか、知ることができますか？

ありがとう

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 の定理または正規言語のポンピング補題を使用して、言語が正規であると仮定することから矛盾を導き出すことができます。

あなたの言語が文脈自由ではなかったとしましょう。文脈自由言語のポンピング補題を使用して、言語が文脈自由であると仮定することから矛盾を導き出すことができます。

もちろん、言語が決定可能または認識可能でない場合は、さまざまな方法でそれを証明することもできます。