5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

形式言語・形式文法

1 :名無しさん@お腹いっぱい。:2007/02/08(木) 14:59:38 ID:cFqQSoeD0
立ててはみたけど、どうなんだろう?

2 :名無しさん@お腹いっぱい。:2007/02/08(木) 21:25:33 ID:48DlP48K0
祝開店
ポンピング定理の最もシンプルな証明を示せ、はどう?

3 :名無しさん@お腹いっぱい。:2007/02/09(金) 06:23:21 ID:XzXtewTj0
定理というか、一般的には補題だよね。
ベタな例だけど、とりあえずアルファベット{0, 1}上の L = {0^n 1^n | n∈自然数} が、正則言語でないことの証明が一番シンプルかな。
それとも反復補題そのものの証明の方?

4 :名無しさん@お腹いっぱい。:2007/02/09(金) 21:14:19 ID:bqvrdnfk0
ウン、反復補題そのものの証明の方のつもりだった。

5 :名無しさん@お腹いっぱい。:2007/02/10(土) 10:36:33 ID:axRz77Wf0
pigeonhole principleより自明 Q.E.D.

6 :名無しさん@お腹いっぱい。:2007/02/10(土) 12:07:55 ID:nCFlXY2X0
>>5
これポンピングの方の解答?
それではほとんど感銘をうけないなあ。
そもそもpigeonholeとはあまり関係ないと思うのだが

7 :名無しさん@お腹いっぱい。:2007/02/10(土) 12:56:13 ID:axRz77Wf0
>>6
有限のリソース(文法や機械)から、無限の多様性(言語)を表現するわけだから、ある共通部分をポンプし続けて増やせるはずっていうのがpumping lemmaでそ。
その「数のギャップ」的な部分をpigeonhole principleで説明するのはよくある話なので、関係なくもないと思いますが。

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

8 :名無しさん@お腹いっぱい。:2007/02/10(土) 15:36:44 ID:nCFlXY2X0
>>7
ウン、最初の2行がいいんじゃない?簡潔、本質ってやつ?
ふつう教科書にはもっとグジャグジャ書いてる。あれいただけない。
(pigeonholeはやはりこの補題には無用)

9 :名無しさん@お腹いっぱい。:2007/02/10(土) 18:38:42 ID:nCFlXY2X0
>>7 >>8
最初の2行は、文学的表現を削ればもっとよくなる

10 :名無しさん@お腹いっぱい。:2007/02/12(月) 09:08:52 ID:Fo/sJJ9F0
ちょっと質問です。
既存の文法を拡張する場合、自分で勝手に反復補題を作ってもいいもんなんでしょうか?
2つの文脈自由性のある文法が生成する言語族の、一方が他方の真部分集合であることを証明したいんです。

11 :名無しさん@お腹いっぱい。:2007/02/12(月) 09:46:27 ID:MgKckCOW0
test

12 :名無しさん@お腹いっぱい。:2007/02/13(火) 10:09:38 ID:6HbMIQU70
>>10
自分で証明できるならおk

13 :名無しさん@お腹いっぱい。:2007/02/16(金) 04:36:05 ID:KOhvxsJE0
何だこのスレ?チューリングマシンとかの話?

14 :名無しさん@お腹いっぱい。:2007/02/18(日) 14:31:26 ID:IgnTFgCc0
今時の形式言語って言ったら、DNAとか細胞とか量子とかの方面の基礎理論構築か。

15 :名無しさん@お腹いっぱい。:2007/02/18(日) 18:20:04 ID:MVMTxGxx0
>>14
そういう分野でも形式文法ってあるんだ。
どんなことしてんのか想像できないけど。

16 :名無しさん@お腹いっぱい。:2007/02/20(火) 21:51:59 ID:zIwd38950
P systemとかスプライシングなんちゃらとか・・・?よく知らないけど。
理論としては面白そうなんだけど、バイオ系の知識がなくて尻込みしてしまうorz
DNAコンピュータでNP完全な問題を解いたり、色んな方面で研究されてるみたいではあるんだけどね。
とりあえず誰か詳しい人教えてください、って状態。

4 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)