オートマトン 反復補題を用いた正規言語、文脈自由言語の判定方法

Question

プログラミングではなく、オートマトンに関する質問です。ここで質問する内容ではないとは承知していますが、もしわかる方がいらっしゃったら教えていただきたいです。

実現したいこと

・ある言語を正規言語か文脈自由言語か、そのどちらでもないのかの判定。
・反復補題に用いてよい任意の文字列zを一般的な形で取ることができない場合の反復補題の適用方法。(z=a^sb^tc^(s+t)のように、cの数はa,bの数により決まるが、a,bの数の大小関係が決まらないときの部分集合とはならないようなzの選択を表すことができないように感じます。もしs,tの大小関係で場合分けしても各々は部分集合でしかないように思います。)

試したこと

・ある言語が正規言語か文脈自由言語かを判定できればいいので、まずそのような文法を作ろうとするのですが、作れないと感じたときに、作れないという保証がなく、何をもって文脈自由言語でないと判断できるのかがわかりません。

Answer 1

cの数はa,bの数により決まるが、a,bの数の大小関係が決まらないときの部分集合とはならないようなzの選択を表すことができないように感じます。

sもtも反復長を超えるような場合や、sとtの差が反復長を超えるような極端な場合について考えれば、どちらが長かったとしても矛盾させられそうな気がします。

もしs,tの大小関係で場合分けしても各々は部分集合でしかないように思います。

「任意のものを表現できる」というのを反証するには、当てはまらない例が1つでもあれば、それで十分です。

Comments

[maisumakun]

こちらでも、a^nb^nc^nという言語について、n=pとして矛盾を導いています。

https://ja.wikipedia.org/wiki/%E6%96%87%E8%84%88%E8%87%AA%E7%94%B1%E8%A8%80%E8%AA%9E%E3%81%AE%E5%8F%8D%E5%BE%A9%E8%A3%9C%E9%A1%8C