形式言語・形式文法

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

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

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

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

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

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

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

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

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

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

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

test

>>10
自分で証明できるならおｋ

何だこのスレ？チューリングマシンとかの話？

今時の形式言語って言ったら、DNAとか細胞とか量子とかの方面の基礎理論構築か。

>>14
そういう分野でも形式文法ってあるんだ。
どんなことしてんのか想像できないけど。

P systemとかスプライシングなんちゃらとか・・・？よく知らないけど。
理論としては面白そうなんだけど、バイオ系の知識がなくて尻込みしてしまうorz
DNAコンピュータでNP完全な問題を解いたり、色んな方面で研究されてるみたいではあるんだけどね。
とりあえず誰か詳しい人教えてください、って状態。

ググったら出てきたけど、これどうなん？

http://www.chimaira.org/docs/FLT-Questions.htm

宣伝乙

>>18
宣伝じゃないわﾊﾞｶﾀﾚ

ちょっと混乱してきたので質問です。
例えば、もしNP完全な言語が一つでもPに含まれることが証明されたら、P=NPになるんですよね？

それで今、文法の言語族がNPに含まれていて、なおかつNP完全な言語を生成できることまで証明されています。
これはこの文法の言語族がNPとイコールになるということではないのでしょうか？

（もしイコールだったら、定理としてそのように書くような気がするんですけど、そういう風には書いていないので疑問に思いました）

>>20
TMの計算量クラスと文法の言語クラスをごっちゃにしてる悪寒

>>21
たしかに混乱しているんですが、実際に計算量クラスと言語クラスが比較され、包含関係が示されています。
どういうふうに解釈したらいいんですか？

いやだから、文法システムの言語クラスは、その文法の記述する言語全てに対して多項式時間内に受理するNTMが存在するなら、NPに含まれるというだけのこと。

文法の言語クラス自体は、ある時間（または領域）以内に解けるとか解けないとかそういう意味は含んでいない。
NP-completeなものを1つその文法で記述できたとしても、他のNP-completeなものまで記述できるとは限らない。

一方でPのほうは、DTMで多項式時間内に受理できることを保証するクラス。
NP-completeなものが1つでもPに属するなら、全てのNP-completeな問題も還元によって、DTMで多項式時間内に解けないとおかしい（ほとんどありえないだろうけどね）。

>>23
なるほど、わかったような気がします。
どうもありがとうございました。

> なるほど、わかったような気がします。

ﾜﾛﾀ

追記。
NP-completeなものを1つ記述できても全てのNP-completeを記述できるわけではないからといって、その証明の価値が低いわけではない。
NPに含まれるということは上界を求めることに他ならないけど、NP-completeなものが1つでも記述できるということは、ある意味で下界を意味する。
なぜなら、この1つの事実によって、その文法の記述力はNPのproperなサブクラスには決して含まれないことを意味するから。

>>17
>だが僕は、右線形文法と左線形文法が生成能力の観点から同値である（同じ言語族を生成する）ことがどうも納得できなかった。
>教科書の説明や証明を読めば、確かにそうなのだと一応の確認は取れるのだが、釈然としないのである。

何言ってんのこの人？
形式言語や計算量理論なんて、一見しただけじゃ等価に見えないものでも、理屈をこねくり回して証明していくことの連続やんけ。

キーワード：対称性、双対性、定式化
ヒント：前書き嫁ｗ

つまり正規言語に対称性が欲しいってことか。
つーか、任意の右線形文法と等価な左線形文法を構築する証明と、その逆向きの証明はほとんど全く同じなのに、それ以上にどんな対称性を探っているのかわからんな。

ヒント：理解できなくてもガッカリするな
　　　　人が何に萌えるかは人それぞれなのだから

いや、ガッカリはしていないけど。
そもそもあのページ、文書が結論まで簡潔してませんがな。
ちなみにおまいはあのページのどこに萌えたんだ？
俺は単に自分が萌えなかった理由を書いたつもりなんだが、よほど共感できた点があるなら書いてみそ。
まさかあのページ書いた本人だったりしてｗ

俺はそこの作者じゃねぇ〜が、
この板に常駐してるヤシが
学問の「萌え」を理解できねぇデクノボーである事はよく判った。

くだらねぇ話題にしつこく粘着してくるヤシが
あまりにくだらねぇので
■■■■　終了　■■■■

俺がこの分野でおもしろいと思うのは、新たに文法体系を導入、拡張したり、既存の文法体系と辻褄合わせたり、種々のアルゴリズム考えたりすることかな。
正規言語を定式化し直したいと考えたことはなかったかも。
前に量子力学勉強してたことあるから、その辺の関連付けは面白そうだとは思うけど、何か微妙な感じもする。

閉包性ってどういう意味があるの？
文脈自由文法を２つ結合したりとか、そんなシチュエーションあるのかな？
教えてｴﾛｲ人！

文脈フリー文法っていう和訳を考案した人のセンスは最高ですね

文脈自由よりマシかな

>>35
結合したいときもあるんだよ・・・たぶん
つーか結合って何？

concatenationのことでしょ。
閉方性はCFGに限らず、主に言語族の同値性とか階層定理の証明を単純化するための道具として使う。

反復補題って難しいなぁ
もうダメぽ

>>40
そう？

かんたんだろ

確かにかんたんだ

pumping lemmaは反復補題だけど、pumping argumentは何て訳すの？

age

wikipediaに載っていたのだけれど
文法AとBに対して
L(A)⊂L(B) かどうかは判定できないんだね
計算機って無力だ･･･

集合演算とか、統計演算とか、確立計算とかを高度に
サポートした高級言語は無いのか？

Mは近いんじゃね

ファジーやニューロモデルの演算をサポートした高級言語は
ありませんか？あと連想記憶モデルとか。

今オートマトンの問題につまずいているのですが
こちらで質問させてもらってもいいでしょうか＞＜；
オートマトン関連の後に形式言語などを勉強したので関連あると思って；
それかどこかいいスレがありましたら教えてくださいorz

>>50
まずはオートマトンの意味を正しく理解してから（ｒｙ

　　「「　(案)投票税、投票税による国民の為の政治を考えるかい、147かい。　」」　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　**　2008.20.12.15.173　**
**　裁判員制度は恐怖政治への踏絵　**

「どうでもいいけど、宗教弾圧じゃ在るまいし、踏絵はないだろう」
「封建制度は支配者の言い分で社会を支配するね。殺人事件にはその時代の
　制度が大きく関わる。よく、政治がらみの自殺や殺人があるけど政府や政治家は
　深く追求をされたら困る訳なんだ」
「国民が参加する事で政治などのカラクリが見えるのではないか」
「それは逆なんだ、人間の心境は中心部に近づけば近づくほど、同化する傾向に
　ある。「郷に入っては郷に従え」と言うよね」
「それに国民が参加する事で、裁判の短縮と審議の簡素化を進めるだろう。
　その殺人の本質を見ることができない状況が生まれる。単に人を殺す事は
　良いか、悪いかだけで判決をするような裁判になる」
「それに殺人資料の秘密保持は国民がその裁判に参加する事で、国民全てが
　理解した事になり、その判決に対しての不満がいえない状況が発生し、非常に
　支配者側の有利な裁判が行われる」
「不十分な審理でも、その裁判に参加する国民の顔色を見ながら、自由に判決の
　方向を示し、支配者の意向に沿った判決が言い渡されるのではないか」
「国民による踏絵は国民からの不満を封じ込み、国民の皆さんが望んだ事です。
　それに国民の裁判員が判決を下したのですよ」
「しかし、選択された国民は裁判員になりたい人とは限らず、決められた時間内での
　判決を心がけ、極力疑問点を訴えないで、目の前の資料だけで判断をするの
　ではないか。私たち国民が認めた裁判員制度はどのように考えても国民に
　利益になる事は一つもないと言えないか」

では非形式言語は存在しえるのだろうか？

自然言語

　　「「　(案)投票税、投票税による国民の為の政治を考えるかい、148かい。　」」　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　**　2008.21.3.9.174　**
**　裁判員制度は憲法違反　**

「裁判官と裁判員は同じ立場なのか」
「それは違うだろう。しかし、判決に関わる訳だから、同じと考えられるね」
「それだったら、憲法違反ではないか」
「裁判官は憲法で独立してその職権を行ひ、と書かれているけどね」
「日本人て結局、どうでもいいのかな」
「そうかな」

**　定額給付金と日本人　**

「定額給付金２兆円のバラ撒き、決まったね」
「決まった。おかしな国だね。税金なんだよな。結局、国民が馬鹿なんだろうな」
「税金て、集めるのに公務員に特別手当のよう金払うのと違うか、今度はその
金をただばら撒くのに特別手当払ってばら撒くのを許したね」
「２兆円って、一万円札で２０キロの高さなんだよ」
「相変わらずの表現だね。２億円の仕事が一万件もできる金額なんだな」

**　海賊制圧も憲法違反　**

「海賊制圧に自衛隊の派遣も決まったね」
「決まったのか。それも憲法違反か。どうなってるだ。日本は」
「日本人って憲法違反が好きなんだな」
「そういう問題か。真面目に成れないな」

雑談スレ2
http://science6.2ch.net/test/read.cgi/informatics/1236656505/l50
立てましたのでそちらでよろしく。

　　「「　(案)投票税、投票税による国民の為の政治を考えるかい、149かい。　」」　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　**　2008.21.3.10.175　**
**　裁判員制度は憲法違反　**

「憲法は日本人に取って最高の規則なんだ。沢山ある法律は憲法が基本」
「憲法に書かれていることを国民が守らなかったら何が国民を守るというの」
「国民は憲法で公平な裁判を受ける権利を認められている。第３章第３７条」
「裁判員として裁判官の知識を学んでいない一般の国民が裁判の判決に関わる
事は憲法違反で無くてなんなんだ」

**　定額給付金と日本人　**

「テレビを見ると給付金を貰って喜んでいる人ばかり、日本人ってがっかりだな、
テレビも国に逆らわない、テレビ局員は平均年収が１５００万円らしい、勉強できる
から給料が良いらしい。馬鹿な番組ばっかりで芸人の出演料も相当良いらしい」
「貧乏人のひがみが始まったな、しこたま給料もらい、馬鹿言って莫大な出演料を
もらい。そんな連中が給付金の一万二千円を貰って喜ぶ国民を見て、みんな嬉そう
という、２兆円がこなごなに砕かれ、一万二千円か、確かに税金の使い方に
しては芸がないね。そして、それを喜ぶ国民とテレビ局員は似た者同士か」

**　海賊制圧も憲法違反　**

「北朝鮮と海賊、こっちも似た者同士、世の中分らない事だらけ、結局、北朝鮮を
海賊にしたのと違うか。自分たちはロケットもミサイルも作り放題、しかし、北朝鮮
はだめ、北朝鮮がロケットを撃ったら、それを打ち落とすと言うわけだよな」

「そんな事を言われたら、怒るだろうな、怒るよ、それが目的か、日本も同じ事を
言っているけど、結局、抑止力なんて嘘ぱち、北朝鮮が衛星って言っているんだか
そう思えばいいと思うけど、どうせ、日本は射程に入っているんだから」
「米国さ、米国に届いて欲しくない。それだけさ、正義も法律も何も無い」
「そんなものかね、強者の言い分は弱者には分らないし、弱者の言い分は
強者には分らない。何れにしても、米国は戦死している人が多すぎる。恐ろしい
国なのは確かだろうな。平和な国でない事は世界中が認めている、日本以外は」

　　「「　(案)投票税、投票税による国民の為の政治を考えるかい、150かい。　」」　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　**　2008.21.3.11.176　**
**　裁判員制度は憲法違反　**

「憲法と法律の区別は日本国憲法にこのように書いてあるね。第10章　最高法規
第98条この憲法は、国の最高法規であつて、その条規に反する法律、命令、
詔勅及び国務に関するその他の行為の全部又は一部は、その効力を有しない」
「裁判員は裁判官と同等だから、憲法に記されている裁判官と同等と考えるべきで
法律を作って、その法律が憲法に違反をしていたとき、そんなことは憲法に書い
いないという理屈はたたないだろうな」

「なぜ、司法が憲法違反までして、殺人事件を国民に任せるんだ」
「まずは憲法軽視だろうな、結局、殺人事件なんて貧乏人のする事でそんな事件は
国民に任せて、公務員には関係ないということじゃないか。公務員の怠慢と言う事さ」

**　民主国家と共産国家　**

「日本てさ、民主国家だろう。でも、公務員たちの生活を見ると共産国家そのもの
だろう。公務員だけではなく、大企業も含めてかも知れないね」
「国民の財産１５００兆円を公務員と大企業が全て使い果すような感じだな、その
生活は共産主義のように働かなくても法律で自分たちの身分と収入を決めて、
毎日、適当に生きていればいい人たち、こんな国が民主国家のはずが無いよ」
「抑止力なんて、共産国家と同じ、何一つ世の中の状況判断がない。よく聞くのが
最悪を考えてだって、正に共産主義だね。金が在ろうが物質的に無理な予算でも
そんなことは関係なく、自分たちの軍事力を確保するという考え方なんか、共産
主義そのもの、呆れるね。結局、抑止力も公務員だろう。共産主義者とも言えるね」

**　定額給付金は憲法違反　**

「そう言えば、定額給付金なんか共産主義国以上に共産的だな。上から下まで
同じ、右から左まで同じ、馬鹿じゃないか、２兆円を国民全員に定額でばら撒く
ことが景気回復だって、そんなことより、憲法を守れ」
「憲法にはこう書いてある。第25条　すべて国民は、健康で文化的な最低限度の
生活を営む権利を有する。失業者が路頭に迷っている中で、税金２兆円をばら撒き
国民が生活に困っているのに貴重な税金を生活に困っていない裕福な人にまで
一万二千円を配る事は憲法違反と言えないか」
「言えるな、公務員ってさ、法律を守らないで、国民が困っていてもほっとくね。
例えば公園で寝ている人たちをほったらかす。本当ならば保護すべきなんだ。
しかし、保護すると金が掛かる。だから、ほっとく、自分たちの給料はそれで
減らない。共産主義と同じなんだ」

新スレ立てたのでどうかよろしくお願いしますだよ(泣)
http://science6.2ch.net/test/read.cgi/informatics/1236656505/l50

オートマトンを最初に考えた人って誰？