形式言語・形式文法

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 14:59:38

立ててはみたけど、どうなんだろう？

**名無しさん＠お腹いっぱい。** · 2007/02/08(木) 21:25:33

祝開店
ポンピング定理の最もシンプルな証明を示せ、はどう？

**名無しさん＠お腹いっぱい。** · 2007/02/09(金) 06:23:21

定理というか、一般的には補題だよね。
ベタな例だけど、とりあえずアルファベット{0, 1}上の L = {0^n 1^n | n∈自然数} が、正則言語でないことの証明が一番シンプルかな。
それとも反復補題そのものの証明の方？

**名無しさん＠お腹いっぱい。** · 2007/02/09(金) 21:14:19

ウン、反復補題そのものの証明の方のつもりだった。

**名無しさん＠お腹いっぱい。** · 2007/02/10(土) 10:36:33

pigeonhole principleより自明 Q.E.D.

**名無しさん＠お腹いっぱい。** · 2007/02/10(土) 12:07:55

>>5
これポンピングの方の解答？
それではほとんど感銘をうけないなあ。
そもそもpigeonholeとはあまり関係ないと思うのだが

**名無しさん＠お腹いっぱい。** · 2007/02/10(土) 12:56:13

>>6
有限のリソース（文法や機械）から、無限の多様性（言語）を表現するわけだから、ある共通部分をポンプし続けて増やせるはずっていうのがpumping lemmaでそ。
その「数のギャップ」的な部分をpigeonhole principleで説明するのはよくある話なので、関係なくもないと思いますが。

ちなみに感銘を受ける証明ってどんなの？

**名無しさん＠お腹いっぱい。** · 2007/02/10(土) 15:36:44

>>7
ウン、最初の２行がいいんじゃない？簡潔、本質ってやつ？
ふつう教科書にはもっとグジャグジャ書いてる。あれいただけない。
（pigeonholeはやはりこの補題には無用）

**名無しさん＠お腹いっぱい。** · 2007/02/10(土) 18:38:42

>>7 >>8
最初の2行は、文学的表現を削ればもっとよくなる

**名無しさん＠お腹いっぱい。** · 2007/02/12(月) 09:08:52

ちょっと質問です。
既存の文法を拡張する場合、自分で勝手に反復補題を作ってもいいもんなんでしょうか？
2つの文脈自由性のある文法が生成する言語族の、一方が他方の真部分集合であることを証明したいんです。