☆オートマトンをﾏﾀｰﾘ語るスレ☆

マターリ

2げっつ

せんせいっ！

オートマトンとオートマトンは何が違うんですか？

性器表現

じゃなくて

オートマトンとオートマータは何が違うんですか？

自動羊ってうまいの？
電気羊の仲間？

singular or plural

テューリング奇怪

有言実行！
小泉は有言不実行！

せんせいっ！

オートマトンがたくさん集ったのがオートマータなんですね。

これシラバスで一際目を引く名前だよね･･･
どんなんなんだろう･･･。

おまんたばやしは三波春夫です！

幽玄慧

(A,S,τ)
S：集合
A：集合
τ:S×A→S

経営板に載っていた↓の問題解いてよ！

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

有名な（？）天使と悪魔の命題です。

ニ分岐の分かれ道があり、その先には天国と地獄があります。
分かれ道にはそれぞれ天使と悪魔が一人ずつ立っており、
全く同じ容姿、声をしており瓜二つ。
ところが、天使は本当のことしか言わず、悪魔は嘘しか言いません。
また、天使と悪魔はお互いのことは知っています。
どちらかに一回だけ質問できるものとします。
どちらに、何と質問すれば、天国へ行く道がわかるでしょう？

http://www.mathcs.sjsu.edu/capow/

連続オートマタなるものがありますが、何か？

オートマトンの何を語ればいいんだ？

理論か？実装か？
もう少しネタフリを絞ってくれ。>>1

>>15
＞どちらに、
どちらか分ってたら、最初から聞かねぇ〜っつーの！

>>15
むちゃくちゃ有名じゃん…
「あなたはどちらから来ましたか？」
じゃないの？

天使は天国から、悪魔は地獄から来てるとは限らない？

悪魔が地獄から来てて、天使が天国からきてたら、両方とも「天国です」って答えるんじゃないの？

>>20
来た方向を指させる。すると、両方とも天国を指す。

あなたが天使である iff 右の道は天国に続く ？

これなら悪魔が天国から来てても大丈夫かと。

「あの方（と話しかけていないほうを指して）に『天国はどちらですか』
と聞いたらどちらと答えると思いますか」と聞く。
もし話しかけたのが悪魔なら、「あの方」は天使ということになり、正しい
方角を教えてくれるはずだが、答えるのは悪魔なので地獄を指す。
話しかけたのが天使なら、「あの方」は悪魔ということになり、間違った方角
を教えてくれるはずで、答えるのが天使なのでそのまま地獄を指す。
ということで、どちらに話しかけても地獄を指してくれる。

どうでもいいけど、オートマトンと全然関係なし。

はーん。そうか。

「あなたはこの先どこに続いているか知っていますか？」
じゃダメ？

>>24
「知ってる」「知らない」という返事しか返ってこないかも

それでＯＫやん。

>>23
正解

『天国はどちらですか』は『地獄はどちらですか』
でも正解

>>27
>>19, >>21, >>22, >>24は？

直接聞くと、
天使*天国=天国
悪魔*地獄=NOT(地獄)=天国

あの方に、、、は
天使*悪魔*地獄=NOT(地獄)=天国
悪魔*天使*天国=NOT(天国)=地獄

と経営板に書いてあった。

>>22
正解やん。すげ！

「右の道は天国に続く ？」
だけでＯＫのような

オートマトンはどうした？

>>31
だめ

そもそも、その二人 (天使と悪魔) が正解を知っているとは
限らないではないか。
それも考慮に入れて答えを出すべきだと私は提案したい。

「どちらのに逝けば貴方の国の住人は増えますか？前のレス読まずにカキコ」
はどう？
左を選んでいた場合
天使：「こっちだモナ（　´∀｀）」→そのまま進行→天国逝き
悪魔：「あっちだニダ＜ゝ｀∀´＞」→進路転換→!地獄逝き＝天国逝き
ただし、悪魔が「>>15に謝罪と賠償を請求しる」っていったらGameOver

>>34
どう答出すんだよそれ

>>34
それは小泉内閣に国政の方向性について聞くようなもんか？

オートマトン・リップトーク

おぉ、トマト。ん？

逢ふと股

逢ふ十股。。ﾊｧﾊｧ

この板はレベル低いな（ｗ

>>15
「（自分が来たばかりの道も含めて）天国に続く道を全部教えてください」
２つ答えれば悪魔。１つなら天使。どっちにしても正解は一目瞭然。

>>43
斬新

>>43
あのさ、それでよ、相手が悪魔でよ、
両方とも天国だって言われてよ、
じゃあどっちの道を選べばいいんだよ。
天国行くのが問題なんだろ？

極度の方向音痴で1人で家に帰れないかわいそうな>>45

>>46
題意理解してるか？

「自分の来た道も含む」んだから、>>43 は正しいような気がするけど…

自分って、悪魔のことじゃなくて、質問者のことか。

しかし、質問者が第3の道から来た、なんて問題に書いてないぞ。

> 「（自分が来たばかりの道も含めて）天国に続く道を全部教えてください」

これにどう答えれば嘘で答えたことになるのかが
まずよくわからないんだけど。
道が3つあるとして、“天国に続く道を全部教えて、
そういう道だけを教える答”以外の答は(2^3-1)通り
あるから、その7通りは全部嘘にカウントされるん
じゃないの？

集団ネタ・・・

有向グラフを用いて・・・

>>43が面白い！と思ったが、>>51がいいこといってるかも。

正解は「誰か偵察に逝かせる」だろ！
っとに、それくらいわからないのかよ！

>>43
ちょっと>>51とかぶり気味だが、
「天国に続く道は１つもありません」は「嘘」なのだから、
悪魔はこのような答え方をする事が出来る。
問題となっているのは
「どちらに、何と質問すれば、天国へ行く道がわかるでしょう？」
なのだから、>>43のような質問では駄目。

>>55
全然面白くない。全く。ほんと、つまらない。「荒らすな」と言ってやりたい。
「荒らし防止」の呪文を覚えて、俺のMPが尽きるまでその呪文をおまえにかけ続けたい。
早くレベルが上がってその呪文を覚えたい。

正解は「誰か偵察に逝かせる」だろ！
っとに、それくらいわからないのかよ！

>>57
偵察の身になって考えてみれ！

>>57
どっちに行った偵察も帰って来ないんですけど！

>>56を見てムキになってる>>57=>>58=>>59はこのスレの趣旨「ﾏﾀｰﾘ」に反するので、
今すぐに退スレして下さい。お願いします。

>>57と俺は別人だよう
>>58, >>59でまたーりできるかと思って
実験レスしてみたんだよう
面白くなかったなら逝ってくるから
許してくれよう

>>58=59
ごめんよう。

>>57
オマエはウザイ。

あ。そうだ。オートマトンって知ってる？＞62

正解は「誰か偵察に逝かせる」だろ！
っとに、それくらいわからないのかよ！

オートマトンを語る奴はいないのか？

オートマトンについて話したいよ！
オートマトンとは何かを教えてください。

ttp://www.suelab.nuem.nagoya-u.ac.jp/~suematsu/zasiki/cha_renzoku.jpg

Oh, Tomaton!

久しぶりに再会したトマトン氏に声をかけるときの言葉です

ノードを生成するようなオートマトンってどう？

>>69
もう少し詳しく説明してくり。
トリガによっては新たな状態ができるということか？
それでは系はどう定義するんだろう？
それでも有限なオートマトンは存在しうるのか？
？？？？？？？？？？？？？？？？？？？？？？？？？？ｸﾞﾙｼﾞｲ........早く説明を〜〜〜〜〜〜>>69

>>69
ニューロンネットワークのようなオートマトンだな。
ノードを生成するエージェント志向もキモイ。

自己書換え可能なオートマトン＝チューリングマシン

>>72
チューリングとの交流でオートマトンを思いついたとされるフォン＝ノイマンの立場は・・・

ネタふり
C言語のコメント文を受理する正規表現は？

／＊[^＊]*＊＊*([^＊／][^＊]*＊＊*)*／

先生！できました！

オーツ麦と羊肉を使った料理

>>69
説明説明説明説明説明説明説明説明説明説明説明説明説明説明説明説明

>>72
チューリングマシンがどしたの？
なんのネタフリ？

>>74
有限系の言語理論だったら、構文チャートで十分。

キャラでは書きにくいが、

→「/」→「*」→「任意」→「*」→「/」→

※「任意」のとこループ
※「/」と「*」の間は改行コードのみ有効

>>70
そそ。あるイベントで新たなノードが生まれる。
ノードの数（メモリ容量？）に制限があるならチューリングマシンみたいなもんか…
つーか全然知らんといってるんだがな。
その前に構造を変化するようなオートマトンを考えなければ…

/*/*/*/*/*/*/*/*/*/*/*/*/**/でも１コメント
つーか、大昔、メイン開いてコメント開いて、閉じ忘れたら、エラーが一個も出なくて喜んでたな。（遠い目

Ｃ言語では、コメントのネストは許されないと思われ

>>81
オートマトンで述べるように

>>80-81のつもりで書いたけどどうよ。
/* .... *
ときて、次が「/」なら受理、「*」ならまた同じ状態に、
それ以外なら*が出る前の状態に戻る。ての

オートマトンはこう：
(0,／＊)→1
(1,[^＊])→1
(1,＊)→2
(2,[^／＊])→1
(2,＊)→2
(2,／)→((3))

状態(1)＝直前に、「*/」になりうる「*」が出ていない状態
状態(2)＝直前に、「*/」になりうる「*」が出ている状態

〓〓〓〓〓
　｜〓｜
　｜〓｜
　｜〓｜
　(⌒⌒)
　 ＼／
　　〓
　【チンコお守りレス】このお守りを見たあなたは超超超幸せ者！
2週間以内に必ず彼氏・彼女が出来るよ！
すでにいる人は超〜ラブラブ　みんなが幸せになりますように…
そのかわりこのコピペを１時間以内に、5つ別のスレに貼り付けてね・・
でないと、あなたはインポや性病になります。

(・∀・)ﾔｯﾀ!!

オートマトンってステータスにトリガーが入ると即座に定義されたステータスに移っちゃうから、
シーケンス機械やコンパイラプログラムなら適用しやすいだろうけど、
現実の世界って、遷移のところに確率が入ったり、待ち行列が出来たりするよね。
そういうのって、どう考えるとシンプルなの？

いい本とかでもあったらおせぇて（♥

非線形複雑系？

混沌系

>>86
やぱ、「シミュレーション」と「計測」でしょ。
高額シミュレータで。

カオス系

それより、非カオス系を発見できたら、それこそハッピーハッピー？！

ライフゲームの１コマをそのまま素子にしたら面白いだろうな。
LEDつけて。全員非同期で動くの。超高速シミュレーション。
たぶんどんなノイマン型コンピュータのシミュレーヨンより速いでしょ。
回路は難しくないがただコスト的に…

数学的なスレだ（遠い目
こういう創造的なスレを待っていた（涙目

チューリングマシン　ＶＳ　非決定性オートマトン

じゃんけん　ぴょん　　のじゃんけんピョン！


はい。　　ぐー

トリガー!!

>>84
チューチングマシンかよ

かあさん。
オートマトン　と　オートマタ　　　　面白かったのはこれしかなかったよ・・

　棚からぼたもち

　有限性オートマトン(嘘)

オートマトンの実装って、
コンパイラ、通信ソフト、シーケンス制御
以外に何がある？

数値計算ツール　ＶＳ　オートマトン　


使う？

非論理型推測妥協安定性オートマトンvs完全論理型決定性人間

アンケート調査(人間）　vs　有限オートマトン(ラヴマシーン)

決定木には様々なオプションがあり、それが1段目、2段目
の分岐の様子を変えると、同一のデータに対する最終的な
解はまったく違ったものになる　ーーーどっかの参考書

決定木の場合はこういうことらしい

ｹﾃｰｲ
つーか、オートマトンの話を一席

昔々在る所にオートマに乗った豚がおりましたとさ。（ﾁｬﾝﾁｬﾝ

くそ。情報工学め
数値計算なんぞ、ねちねち取りageやがって、
オートマトンのほうが楽しくていいだろ
先に取り上げろよ。数値はsageでいいから

>>105
教授が苦手な抗議は後に廻して、煙にまくものよ。

　そうか？数値解析はおもしろかった。どこがったって、手間がn^3からn^2になるんだぜー。

情報工学かー。シャノンの定理とか、その前の情報エントロピーの定義とか
やっぱおもろかったＹＯ。

おぉトマトんﾉﾊﾅｼﾊ?

Automatonでいいのかな？スペルは。
オートマ、ンン！（tが消えかけ）みたいな発音でしたっけ。
ちょっとセクシーボイスっぽい感じで。ンンのところが。
24歳なネイティヴおねいさんに読んで欲しいな☆

RS232C　コンポーネント vs　TCP/IP　コンポーネント

トリガー!!

ＲＳ２３２は２０世紀最大の発明です。

Ｃを忘れた。でも、Ｃ言語も２０世紀最大の発明のうちの１つです。

awk　　vs　　C/C++


トリガー!!

ライフゲームがどうしたの？

コンウェい？

一番、正規表現を実装したくない言語　→C言語

オーマタ性器表現

とりあえず聞いてみるけど、
この中で非決定性オートマトンと決定性オートマトンの等価性証明、
自分で出来る人どれくらいいる？

とりあえず聞いてみるけど、
この中で非決定性２チャンネラーと決定性２チャンネラーの等価性証明、
自分で出来る人どれくらいいる？

とりあえず聞いてみるけど、
この中で非決定性（・∀・）コピパ！！と決定性（・∀・）コピパ！！の等価性証明、
自分で出来る人どれくらいいる？

非決定性（・∀・）コピパ！！ = （意味不明）‥‥‥(1)
決定性（・∀・）コピパ！！ = （意味不明）‥‥‥(2)
(1), (2)より、
非決定性（・∀・）コピパ！！ = 決定性（・∀・）コピパ！！
（証明終）

「オートマトン」は、
レートロマン語の「オートメーション」です。

「サウラビ」は、
韓国語の「さむらい」です。

階層型ネットワーク　vs　状態遷移図

vs シリーズ辞めろよ！
つまらん

オートマトンの中身がわからんならだまっとけ

125vs126

126 vs 127

オートマトン　vs　チューリング機械

　あ、すいません。数学事典で調べます（ヤフーで調べてもいいんだよな）。

モヤシを食べていました。
そうするとどうでしょう、壁の穴から例の珍虫がまた現れたではありませんか。

オートマトンのトリガー、確率と行列と

股狸

あー。Ｃ言語は使えない言語やね。
これでオートマトンをやろうとした馬鹿やったわ。シーケンスはしたこと
ないけど。
awk　いいね。これ。ちょー簡単だわ。
これにぼこぼこ正規表現とトリガー、あてはめていけばええやん。
なんでいままで手つけなかったんやろ

駄文。

Ccomment受理オートマトンをVHDLでモデリング。

process(c,state) is
case state is
when 0 => next <= 1 when c='/' else 0;
when 1 => next <= 2 when c='*' else 0;
when 2 => next <= 3 when c='*' else 2;
when 3 => next <= 0 when c='/' else 2; isAccepted <= true;
end case;
end process;

めちゃ単純！

D1　=　Q1　+　Q1_・Q2・*
D2　=　Q1　+　Q1_・Q2_・/　+　Q1・Q2_・*
OUT　=　Q1・Q2・/
回路実装も簡単！

修正！
D2　=　Q1_・Q2_・/ + Q1・Q2_・*

　ＤＮＡもオートマトンの一種じゃないのか？

>>137

|￣￣￣￣￣￣￣￣￣￣|
|　電波を感知しました｡　|
|＿＿＿＿＿＿＿＿＿＿|
　　　　　　　　　　　　　　／　／
　　　　　　　　　　　　　　／
　　　　　 ＿　　　　　　　　　ﾋﾞﾋﾞﾋﾞ
　　　　 /||__|∧　　　 ／
　　。.|.（Ｏ´∀｀）　／
　　|≡（ ))　　))つ
　　｀ー｜ ｜　|
　　　　（_＿）＿）

つーか、DNAをタンパク質にデコードする、なんとかゾームとかの解釈システムは、
まあオートマトンといえなくないかもしれん。
でも免疫系のいろいろとかあるし、きっとそんなに単純じゃないよ

ﾃﾞｵｷｼﾘﾎﾞ-ﾄﾏﾄﾝ

ﾆｺﾁﾝｱﾐﾄﾞｱﾃﾞﾆﾝｼﾞﾇｸﾚｵﾁﾄﾞﾘﾝｻﾝﾏﾄﾝ

awk　にちょろっと書いて
cvs形式のテキストフォーマット食わせれば
ちょいっとなっと、料理できるな。
それだけだけど

ここはオートマターリをﾏﾄｰﾝ語るスレですか？

>>138 >>139
別に１３７はそういうことを逝っているのではなくて、最近はやってて、そろそろすたれそうな、
ＤＮＡコンピューティングのことをいってるのではなくて？

>144

自己増殖機械いわゆるセルオートマトンのことだろ。

>>142
×cvs
〇csv comma separated value

マトンヌ

オートマタンキ

・・・

オトータマ

>>146
正論

>>143
×ここはオートマターリをﾏﾄｰﾝ語るスレですか？
○ここはオートマタリをﾏﾄｰｿ語るスレですか？

オートバックス 待ったり

>>150
正論

>>152
正論

サウンドノベルはオートマトンですか？

お゛ぉ〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜
ﾄﾏﾄﾝ

おどま　ぼんぎり　ぼんぎり 盆からさ〜きゃ　お〜らんど

automaton（単）
automata（複）
らしいでっす

アナログ情報を扱うオートマトンとかどう？
状態も離散的じゃなくて連続的。

［問題]
オートマトンＡとオートマトンＢが変則ポーカーをするとする．
ルールは次の通り．
　１）ゲーム終了後，ダイヤの枚数が相手より多ければ勝ちである．
　２）オートマトン達は次のａ，ｂ，ｃの３パターンの行動のいずれかひとつを選ぶことが出来る．
　　ａ）手札の中の好きな１枚をごみ箱に捨て，山札から１枚を拾う．
　　ｂ）パス．１枚も交換しない．
　　ｃ）ストップをかける．
　※パスするときには捨てて拾う振りをすることとし，相手にはａとｂの見分けがつかないとする．
　※ストップをかけると自分はそこで終了，相手はもう１回だけａまたはｂのいずれかを実行することが出来る．
　３）手持ち札は常に５枚である．
　４）山札には無限組のトランプが用意されているとする．

さて，オートマトンＢは，自分のダイヤ枚数が５枚未満のときａを，
５枚のときはｂを選ぶように設計されているとする．（ｃは実行しない）

オートマトンＢに対する勝利の期待値が最大となるようなオートマトンＡを設計せよ．
（なお順番はオートマトンＡから始まる）

>>86
マルコフ連鎖

http://www.elc.nias.ac.jp/~nagasaka/lect/ic/1999/OHP/I03/sld012.htm

こんな本はどうかな

岩波情報科学 ソフトウェア科学〈12〉/計算モデルの基礎理論
http://www.amazon.co.jp/exec/obidos/ASIN/4000103520/qid=1022421385/sr=1-10/ref=sr_1_2_10/249-3894865-7608327
計算理論の基礎　　共立出版
http://www.amazon.co.jp/exec/obidos/ASIN/4320029488/qid=1022421385/sr=1-7/ref=sr_1_2_7/249-3894865-7608327

ファジ理論のメンバーシップ関数が良く分かりません。
出力にとりうる値が0or1に限定される筈なのに、どうして
0.3やら0.8やら出てくるのでしょうか？

限りなく 1　に近い

.com

マターリ

自動羊肉

☆オートマトンをｺｿｰﾘとｸﾞﾀｰﾘ語るスレ☆

ｸﾞﾀってないでもっとしゃきっとせんかい！

からくりサーカス

みんなで隠れマルコフやろうよ

コラッツ予想（偶数なら２で割る、奇数なら３倍して１足す）は
チューリング機械で記述して受理するかの判定では解けないのでしょうか？

⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y⌒Y☆　　*
　.人　　　人　　　人　　　.人　　　人　　　人　　　.人　　　人　　　人　　　.人　　　人　　　ﾉ　　　　☆
／　.＼／　 ＼.／　 ＼.／　 ＼／　 ＼.／　 ＼.／　 ＼／　 ＼.／　 ＼.／　 ＼／　 ＼.／　☆

>>178
少なくともそれだけでは解けないんじゃない?
チューリング機械停止性問題は計算不可能でしょ。

>>180
安部氏！

面白い問題考えた。

M0=(Q0, Σ0, δ0, q00, F0)
M1=(Q1, Σ1, δ1, q01, F1)
のふたつのオートマトンがある。

これらに同時に同じ系列を与えていったとき、
どちらか一方が受理したときに受理するような
新しいオートマトンＭを作りなさい。

http://science.2ch.net/test/read.cgi/math/1030099283/l50
　　

>>182
状態を2次元化して最終状態を緩く整備すれば。。
Q := {(q0,q1)|q0∈Q0, q1∈Q1}
Σ := Σ0∪Σ1
δ := (q,σ) -> (δ0(q,σ),δ1(q,σ)) ★δ0、δ1の定義域の不一致は適当に処理
F := {(f0,q1)|f0∈F0, q1∈Q1}∪{(q0,f1)|q0∈Q0, f1∈F1}
M := (Q,Σ,δ,F)
ﾀﾞﾒ？

あ、違った
δ := ((q0,q1),σ) -> (δ0(q0,σ),δ1(q1,σ))
こうだな

どうせ直すならこう
Q := Q0×Q1

そう書いちゃうならこう
F := (F0×Q1)∪(Q0×F1)

>>184-187
ご名答です。
定義域の不一致は問題のミスだね。Σ0=Σ1でないと問題にならない。
キモは単に最終状態の定義だけでしたね(汗)
>>187はそうきたか(笑)かっこいいっすよ。惚れ惚れしちゃいます。

じゃ次の問題。

オートマトンM=(Q, Σ, δ, q0, F)がある。
Ｍが１０回連続で最終状態にあるときに
初めて受理するようなオートマトンＭ'を作りなさい。

かっこいい解答をお願いします（あんまりかっこつけるとこないかｗ）

※ところでオートマトンの一般的な定義ってこれで合ってますっけ？

かっこよくはないがこんなんで。。

Q' := Q×ω　　　where ω：非負整数全体
δ' := ((q,n),σ) ->
　　　　(δ(q,σ),n+1)　　　when δ(q,σ)∈F
　　　　(δ(q,σ),0)　　　otherwise
q0' := (q0,0)
F' := F×{n∈ω|n≧10}
M' := (Q',Σ,δ',q0',F')

>>188　定義つーか記号の説明が一応最初にあると親切かもしれない

tu-ka,正直1人で答える俺

マターリと語るのに、初心者向きの練習問題を出します（たぶん、
簡単に解けるんだと思いますが、自分でやってないので、
簡単すぎた場合や、ちょっと難しい場合はご容赦ください)。

コメントの例が出されてましたので、それを拡張した次の
問題を解いてください。

コメントがネストしても対応が取れるかぎりOKという場合、
例えば、
　　/* /* /* ... */ ... /* ...*/ */ */
こんなの。これを受理する有限状態のオートマトンはないことを
証明せよ。「/*」と「*/」が2文字で面倒なので、これをa と b に
してもう一度問題を書いておきます。

文字は{a, b, c}。a がコメント始まりで、bがコメント終わり。
受理する文字列は a で始まりbで終わる。a と b の間には
a, b, cが任意の個数表れてよいが、bが現れるときは対応する
コメント始まりの a が必ずあること。このような文字列を
受理する有限状態オートマトンはないことを証明せよ
（ないよね？　勘違いだったりして）。

オートマトンって数学の分野なんですか？

193の補足。これは
　「bが現れるときは対応するコメント始まりの a が必ずあること」
という未定義用語を定義するところから始めないといけないので
テストの問題などとしてはよろしくないかもしれませんが、ここは
お勉強で、そこからはじめるということで。

>>188
問題の意味が分からないのですが
> Ｍが１０回連続で最終状態にあるときに
> 初めて受理するようなオートマトンＭ'を作りなさい。
これは、Ｍが受理する言語をＬとするとき
　　Ｌ＾１０＝ＬＬ．．．Ｌ　（１０回）
　　（ あるいはアルファベットをΣとして、Σ* (Ｌ＾１０) Σ*）
を受理するオートマトンを作れという意味ですか？　気になって
いるところは「Ｍが１０回連続で最終状態にあるとき」で、言葉
通りに受け取ると、入力列があって、どこかで最終状態に入って、
そこから９文字の入力で、最終状態から抜けなければＯＫと言うように
きこえるところです。

>>193
全状態数K個の受理可能な系列を持つオートマトンの集合をμ(k)とする。
ある途中の状態a0から考えて
a0→a1→a2…an→ b0→b1→b2…bm→「b0」→c1→c2…cl→f(f∈F)
のようなループを持つ受理可能な系列に対しては必ず、
a0→a1→a2…an→ b0→c1→c2…cl→f(f∈F)
というそれよりも短い受理可能な系列が存在する。
よってある状態にあるオートマトンＭにおいて、
最小の長さで受理するものは、ループを持たない。
（ループを持つならそれより短い受理可能な系列があるので長さが最小に矛盾）

最小系列→ループを持たない

ある途中状態にあるオートマトンに対し、そこから最小の長さで受理できる系列の長さＬminとする。
μ(k)に属するオートマトンの中で、Ｌminが最大になるオートマトンをＭmaxとする。

Ｍmaxとはどんなオートマトンであるかを考える。
Ｌmin――つまり、「ループを持たない受理可能な系列」の長さ
が最大であるようなオートマトンのことである。
これは最終状態が１つでかつ、最小系列を与えたときに、
すべての状態を経て最終状態に至るようなオートマトンで、最小系列の長さLminはk-1となる。
（すべての状態を経ないとk-1未満になり、最小系列が最大に矛盾）

μ(k)の中で残りの最小系列が最大であるオートマトン→受理できる系列の長さはk-1以上

さて、本題>>193を満たすオートマトンがμ(N)の中のもので構築できたと仮定する。
(つまり有限状態数Nを持つオートマトン)
このオートマトンがa^1000Nを受信したとするとあと最低1000N個は受信しないと受理できない。
（全部bでも最低1000N個いるから）
つまり残りの最小系列の長さは1000Nであるが、
μ(k)の中には最小系列の長さが最大でもN-1になるオートマトンしかない。
よってこれは矛盾する。

オートマトンの状態数は有限なので、全てのオートマトンはあるN∈Zを用いてμ(N)に属するといえる。
しかし任意のμ(N)に>>193を実現するようなオートマトンは存在しないので、
題意を満たすオートマトンはどこにも存在しない。

実はageたかった

しかもまだageられてない

>>199　アフォ。
でもある意味面白い書き込みだ。

ageてみる

age

age

age

（＾＾）

またーり

あるプログラムを実行すると無限ループになる可能性があるか否かを判断する
プログラムを作ることはできないと聞いたことがあります。
どなたか、簡単に証明をお願いします

みんなで1次元オートマトンやろうぜ。

ルール
□□□　■□□　□■□　□□■　■■□　■□■　□■■　■■■
　 □　　　　■　　　　■　　　　■　　　　■　　　　□　　　　□　　　　■
　

じゃ、初期条件ね。

□□□□■□□□□□

>>210
ごめん、端の方はどうする？

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
>>211
ループでいいっしょ

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
□□□□□□□□□□□■□■■■□□□□□□□□□□□□

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
□□□□□□□□□□□■□■■■□□□□□□□□□□□□
□□□□□□□□□□■■□□■■■□□□□□□□□□□□

なんかつまんない結果になりそうだな。

ルールが逝かんのよ。

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
□□□□□□□□□□□■□■■■□□□□□□□□□□□□
□□□□□□□□□□■■□□■■■□□□□□□□□□□□
□□□□□□□□□■□■■■□■■■□□□□□□□□□□

あってる？

　　 ,.´ / Vヽヽ
　　　 ! i iﾉﾉﾘ）) 〉
　　　 i l l.´ヮ｀ﾉﾘ　＜先生！こんなのがありました！
　　　 l く/_只ヽ 　　　
　　|￣￣￣￣￣|
http://saitama.gasuki.com/hiroyuki/

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
□□□□□□□□□□□■□■■■□□□□□□□□□□□□
□□□□□□□□□□■■□□■■■□□□□□□□□□□□
□□□□□□□□□■□■■■□■■■□□□□□□□□□□
□□□□□□□□■■□□■■□□■■■□□□□□□□□□

□□□□□□□□□□□□□■□□□□□□□□□□□□□□
□□□□□□□□□□□□■■■□□□□□□□□□□□□□
□□□□□□□□□□□■□■■■□□□□□□□□□□□□
□□□□□□□□□□■■□□■■■□□□□□□□□□□□
□□□□□□□□□■□■■■□■■■□□□□□□□□□□
□□□□□□□□■■□□■■□□■■■□□□□□□□□□
□□□□□□□■□■■■□■■■□■■■□□□□□□□□
□□□□□□■■□□■■□□■■□□■■■□□□□□□□
□□□□□■□■■■□■■■□■■■□■■■□□□□□□
□□□□■■□□■■□□■■□□■■□□■■■□□□□□
□□□■□■■■□■■■□■■■□■■■□■■■□□□□
□□■■□□■■□□■■□□■■□□■■□□■■■□□□
□■□■■■□■■■□■■■□■■■□■■■□■■■□□
■■□□■■□□■■□□■■□□■■□□■■□□■■■□

シェルピンスキーー・ガスケット！！！！！！

１次元セルオートマトンって
f : {0,1}^3→{0,1}
P(x,y)=f(P(x-1,y-1), P(x,y-1), P(x+1,y-1))
てな感じだな

>>221
3近傍で，状態が{0,1}なら状態遷移関数はそれで正しいけど，
5近傍を採ったり状態数を増やしたりしたら，そうはいかないでしょ。

一般には直積位相での連続写像かな。

オートマタ（自動人形）とオートマトンはどのような関係が？
オートマタを状態遷移図で表せる？？

automata=[名]automatonの複数形.

オートマタ
λ
オートマトン
　λλ　λ　λ　λ　λ　λλλ
λλ　λλλ
　　　λλ　λ　λλλ　λ
　λ　　λ　　λλ　λ　λ　λ　λλλ　　λ　　　　　　　　　λ

【何処も】情報科学総合ｽｯﾄﾞﾚ【板違い】
http://science.2ch.net/test/read.cgi/rikei/1046173479/l50

広田良吾と高橋大輔の新刊がでたぽ

（＾＾）

セル・オートマトンって複雑系で使うの？
厨房にわかるよう説明して。

>>232
使わない。
わかったらｶｴﾚ

ここですか、オートマターリをﾏﾄｰﾝ語るスレは。
(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　
　　　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　(ﾟ∀ﾟ)ﾏﾄｰﾝ!!　

（＾＾）

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

最下層スレを一気に浮上age

げこげこ

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

ｵｰﾄﾓｺｰﾘ

ほしゅったらageろ！

http://homepage.mac.com/hitomi18/

自動羊揚げ

age損ねた…(鬱

>>193
これパンピング定理使って解くんだったね。
今頃気づいた。

おれは、これで修士号をとったので、なんでも質問してきていいよ

http://www.k-514.com/
ボッキンキン

>>209
http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/2003/computing/note/7/7.html

n個のオートマトンＭ1,Ｍ2,…,Ｍnがある。
Ｍk=(Ｑ:状態集合, Σ:入力記号, δk:遷移関数, q0k:初期状態, Fk:終了状態集合)

入力Lに対してＭkが一番早く受理するとき(同時受理も含む)にのみ
Ｍklkを受理するオートマトンＭ'を作れ。
ただしΣ'=Σ∪{Ｍ1,Ｍ2,…,Ｍn}とする。

しまった。こうだった

入力Lに対してＭkが一番早く受理するとき(同時受理も含む)にのみ
ＭkLを受理するオートマトンＭ'を作れ。
ただしΣ'=Σ∪{Ｍ1,Ｍ2,…,Ｍn}とする。

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

今大学でオートマトンをやってるんですけど
言葉の説明というより、○○を含む信号列を受理するオートマトン
を設計せよとか、決定性、非決定性のオートマトンを設計する演習しか
してないんですけど、オートマトンの設計がたくさん載っていて
とてもわかりやすい参考書があったら教えて下さい。

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

16

エイトマン

　　　 　∧＿∧　 ∧＿∧
ﾋﾟｭ.ｰ　（　 ・３・） (　　＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
　　＝〔~∪￣￣￣∪￣￣〕
　　＝ ◎――――――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉&ぼるじょあ

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

5

語れ。

26

エイホの「コンパイラ」が良いのでは？

>262
エイホは一部の日本人は”アホ”と読むので。。。以下略

言語 L = {0,1} 上の系列で11を部分系列として含まないものからなる集合をLとする。
Lをあらわす、正規表現を与えよ。
とかあるんだが悩んだ末とけん！誰か教えてくれ〜、せめてヒントくれ

適当＝(10|0)*(φ|1)

２×７×１９。

21

（１０｜０）＊（｜１）。

（１０｜０）＊（｜１）。

(０*１０)*

>>270
それだと1で終われないじゃん

11を部分列として含まないのであるから、
長さ2の列で考えると00、01、10の三つが残る。
これらを組み合わせて01の後に10が続かないように考えれば良い。
つまり、X=00、Y=01、Z=10として、X(X|Y|Z)またはY(X|Y)またはZ(X|Y|Z)である。
これらX、Y、Zは長さ2であるので、長さ1のときで考え重複する部分を簡略化すると、
A=0(A|B)
B=1A
として
S=A|B
となるSが答というのが題意からほぼ直接的に導かれることになる。

これを解くには、まず、A=0A|0B=0A|01Aなので、A=(0|01)*。
そして、S=A|B=A|1Aなので、S=(0|01)*|1(0|01)*が答となる。
空の記号列を使ってよく、それをεで表すとすれば、
S=A|B=A|1A=(ε|1)A=(ε|1)(0|01)*と表しても良い。

アンドロイドは自動羊の夢を見るか

自動羊って何だ。

ageなさい

000

462

9

524

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

二年一時間。

737

オートマトン
まんせー

>>263
げっ，俺もそれ思ったわｗ

>>264
どうでもいいけど，それってFibonacci表現だよね

同上、決定性、１２状態のオートマトンおしえてください＾＾

>>285
どんな言語を受理するDFAを作ればいいのでしょうか?
ちょっと質問の意図が読めません．

0と1をつかいます。丸と二重まるで二重丸が受理するです＾＾

>>287
つまり，Σ = { 0, 1 }．
受理状態とかの記号とかは分かるのだけど，どんな言語を判定するDFAを作ればいいのやら（ ；´Д｀）

＞0をちょうど二つ含むか、または001を含まない8状態

このような含まない状態ってどう表すのですか？
今習っているのは初歩で、

　0　　0
O→O→O受理

みたいなものです。

０をちょうど二つ含む。
０の個数が０か１か２か３以上かで分ける。

００１を含まない。
最後の０の個数が０か１か２以上か００１を含むかで分ける。

>>290
レスありがとうございます
もし001がきた場合はどこに遷移するのでしょう？
スタートに戻るのでしょうか？
それとも、00ときて1がきたらそれは無視してその場にとどまるのでしょうか？

０の個数が０で最後の０の個数が０の状態。
０がくる。
０の個数が１で最後の０の個数が１の状態。
０がくる。
０の個数が２で最後の０の個数が２の状態。
１がくる。
０の個数が２で００１を含むの状態。

状態遷移図で書くとどうなるのでしょう？
図・グラフ掲示板
http://www6.tok2.com/home2/wi2003/cgi-bin/bbs3/bbsnote.cgi
こことかで教えてもらえませぬでしょうか

あと、
〜〜かつ０を一つしか含まない状態
という問題があったとして０がきた後にまた０がきた場合は開始の点に戻ると言うことでしょうか？
たとえば、
http://www6.tok2.com/home2/wi2003/cgi-bin/bbs3/data/IMG_000141.png
で、0の後に0がきて条件に一致しないので、開始の点に戻らせたのですがこれであってますでしょうか？

答えてあげたいけど，問題がよく分からない(汗)

0と1が入力されて、始点と受理の点があるという前提で
たとえば、
0を2回以上含み、かつ1は一つしか含まない状態遷移図というのを考えると

http://www6.tok2.com/home2/wi2003/cgi-bin/bbs3/data/IMG_000142.png
となると思うのですが、？の部分は1が2回目の時なので次に何がこようと受理されないですよね？
その場合はこの矢印をどこにつなげればいいのかなと。

>>295
Javaがうまく動かないので，状態遷移表で勘弁して下さい．

Σ={0, 1}　　Alphabet
Q={q0, q1, q2, q3, q4, q5}
初期状態は q0，受理状態の集合は{q5}

　 　|　　0　　　1
----------------
q0　|　q1　　q3
q1　|　q2　　q4
q2　|　q2　　q5
q3　|　q4　　×
q4　|　q5　　×
q5　|　q5　　×

×は拒否状態になることをあらわします．

多分，これであっていると思う…状態数が減らせるかどうかは分からない

120

772

163

736

IMEのローマ字変換規則をオートマトンにしたい

>>301
振る舞い仕様からオートマトンへの変換なら、
情報系の論文になりまつよ。

910

264

440

最近ツリーオートマトンなるものを習ったんだがなかなか面白い。
応用も多いし。

今まで｢具体的に｣考えられたオートマトンで、
内部状態の数が最も大きかったのは何か?

>>889 キバヤシを貼ろうか、監督を貼ろうか、迷いました。


有名な（？）天使と悪魔の命題です。

ニ分岐の分かれ道があり、その先には天国と地獄があります。
分かれ道にはそれぞれ天使と悪魔が一人ずつ立っており、
全く同じ容姿、声をしており瓜二つ。
ところが、天使は本当のことしか言わず、悪魔は嘘しか言いません。
また、天使と悪魔はお互いのことは知っています。
どちらかに一回だけ質問できるものとします。
どちらに、何と質問すれば、天国へ行く道がわかるでしょう？

Re:>308 何だよ「ニ分岐」って。「二分岐」だろ。

「この道の先に天国があるかと訊かれたら肯定しますか？」

おっとまった

オートマタ

>>309
>>308は、すげぇ五社だったんだけど、その答ってあってるの？

830

621

>>308
天使（悪魔）がメスであれば、問答無用で犯す。
いくらこれから罪を犯しても
天国へ行くか地獄へ行くかは5割であるから。

921

太陽は２つあるか？
天使　いいえ
悪魔　はい
ピンポン

設問が。。。。

インパクトダイヤルは使えるか？
天使　はい
悪魔　いいえ
ピンポン

>>301
母音で区切れ

291

706

可逆セルオートマトンと圧縮理論の関連について語ってくれ。頼んだぞ。

オートマトン＝自動羊肉

474

>>307
オートマトンで素数を求められるか？という無謀な問題を解こうとして
やっきになっちゃった人たちが作ってしまった
途方もない失敗オートマトンが最大だと思われ。

>>307
この間、東急ハンズに最新のオートマトン売ってて、内部状態が１００個くらい透けて見えましたょ。

>>326
iMacが流行ってから世の中ロクなことねえな

数学者はオートマトンの夢を見るか？

俺はチューリングマシンの夢なら見たことあるがオートマトンだけの夢はないなあ。

459

123

264

正則表現で記述できない言語を、言葉で説明するとどのようになるの？
それとも言葉では説明できないの？

760

>>332
「正則言語でない言語」でいいやん…。
それともそのような言語の具体例が知りたいのか？

225

557

441

オートマトンって、
「手も足も出ない」ロボットの事ね。
私嫌い。

>>338
つまりジーグヘッドってことか。
い〜まにみていろ邪魔大王国〜全滅〜だ〜♪

723

帰納的加算とか非帰納的とかいう概念を
定性的に言葉で説明できる奇跡の詩人はここにおられますか？

>>341
＞定性的に言葉で説明
第二階の言葉を使っても良いのですか？

オートマトンの自動生成法おしえて

そうじゃないんだよ
箱玉系，離散ソリトン系なんだよ

　　　　　　　　　　　　　　　　　　　　　　　 ''ﾐ″　　.ヽ l".,lﾞ.,,,_
　　　　　　　　　　　　　　　　　　　　　　　　 `'x,.｀ﾟ''i､ﾞll,,,lメ゜｀~"x,,,
　　　　　　　　　　　　　　　　　　　　 　 　 　 　 ~',u'"｀ ﾞﾟx¬ｰ ,,r″
　　　　　　　　　　　　　　　　　 　 　 　 　 _,,,-‐"｀ﾞﾟＬ.,r'"ﾞﾞ'ｨ''"＾
　　　　　　　　　　　　　　　　　　　 _,,,-‐'ﾞ＾　　　 ._,,,{|*、　 .ヽ、
　　　　　　　　　　　　　　　　_,―''"｀,,,,,――‐ﾆ巛,,、　ヽ、　 ｀'､、
　　　　　　　 　 　 　 　 　 ,ij,ぃ,,,,,｣'" -''''""ﾞﾞ'''-､‘i､ﾞl,,,,,,,.ﾞ'i､　　 ｀'､、
　　　　　　　 　 　 　 　 　 | ｀ﾞン'ﾞ｀、 .,/',,r,,-.,,-　'''“''･,,‘'i､ﾞi､　　　＼
　　　　　　　 　 　 　 　 　 | ,/ﾞ,,-'".,-'ン／,/′　.i､i､i､ ｀ .ヽ‘i､　　、｀'i､
　　　　　　　　　　　　　　 ,ビ'"/`,,i´,/ .″"　　　,lﾞ.| .） │ .|　｀'ｺ'″　 ヽ
　　　　　　　　 　 　 　 　 |'lﾞ ││,,―ｰ''"　 ヽ、’ " .|　.|　 | ,／　　　 ,/
　　　　　　　　　　　　　　｀ l / /,lﾞ ､i″ｭ　　　_,,,ヽ,、｀　.| .,,〃　　　 .,/′ たすけてっ！
　　　　　　　　　　　　　　　 |.| lﾞlﾞ　 |ﾞ'fr"、　 "| ｀''l,、 ,､,!'"　　　　／ 　　　Kingに犯された上に殺される！
　　　　　　　　　　　　　　　 |ﾞl.,!｛ .| ﾞl,　.r‐，　ﾞﾟ'-f广_//¨ﾞﾞﾞ"〕　,-"
　　　　　　　　　　　　　　　 ﾞl.ﾞ' .ﾞl ﾞl､.ヽ.ヽ/　　 ,,/,/ｉジ''''''Ｔ　|,i´
　　　　　　　　　 　 　 　 　 ,!ト .、　″.ﾞ|ヽｗﾆ,,,/,i´'"　　 .| ,/ﾞ|、
　　　　　　　　 　 　 　 　 ,/､lﾞ .lﾞ　　._,､ト-,,,,r'ｹ,i´　　　　,,ﾈ　 ﾞl
　　　　　　 　 　 　 　 _,-'ﾝ゛lﾞ _|,,,-''',ン‐フ”　|.lﾞ　　　　,/　|　　ﾞl,
　　 　 　 　 　 _,,,,,-‐彡',ﾝｯ?ﾞ”゛,／＾　,/｀　.| |.|　　　 ./|　 .ﾞl　　ヽ、
　　　　　 .,,-'"｀ ,／゛r''^,i´　 ／｀'l..) ,!　　 ."'|ﾞl　　 ／ |　　ﾞl　　 ｀'i､
　　　 _,／｀　 ,／　 .,ｽ ｛　　 |　　　　|　　　　ﾞlﾞl　_イ　 ｛　　ﾞl,　　　 ヽ
　　.,,i´　　　／　　,/｀ﾞl ﾞl、　｛　　　　|　 .,,/　 ﾞlﾞl'" |　　.|　　 ヽ　　　 ヽ、

>>345
King様に犯された上に殺される！
この世の極楽味わいながらあの世にいける！

961

みなさん、２ちゃんねる専用ブラウザを使用して、「Re:>」をNGワードに設定しましょう。
「Re:>」をNGワードにすると偽者もあぼ〜ん出来るし、他のトリップを使ってる人を無視しなくて済みます。
kingが名前をしょっちゅう変えるのは、NGワードに登録されてあぼ〜んされるのを防ぐためらしいので、この方法が有効です。

203

所詮世界なんて

プランクの長さのセルでできた
プランクの時間で発展する
オートマトンなのだよ

...orz

>>350
時間は相対的ですが何か

>>350
古典的には、な。

オートな馬肉

まじぼけですよね

490

自動鍋つかみ

118

Visibly Pushdown Languages
ttp://portal.acm.org/citation.cfm?id=1007390

プログラミング言語等複雑な構造を持った言語を表現でき
なおかつ幾つもの演算に関するclosure propertyを満たし
同一性等の決定問題も肯定的に解ける、という
文脈自由言語と正則言語のいい所だけ取ってきたような
言語のクラスについて論じている。

読みたいけど会員じゃないと読めないの?

age

>>359
会員じゃないとダメっぽいね。
これなら読めるかな？Googleで2番目に出るヤツなんだけど。
ttp://www.cis.upenn.edu/~alur/Stoc04.pdf

>>361
thx!
読んでみます。

age

ｾﾙﾗｰｵｰﾄﾏﾄﾝﾓﾃﾞﾙって難しいんですかね？
ム板から来たんでつが(´・ω・`;)

セルラーって？？？
釣りかな…

C言語で、ｾﾙﾗｰｵｰﾄﾏﾄﾝﾓﾃﾞﾙのアニメーションを作りたいんだけど。同志を求めてやってきたんですが。。名前が違うのかな？

Javaで作ってるものは見たことあるんだ。(^_^;)

検索してみたんでつが、情報が凄く少ないんですよ(つд-;)
数学小辞典を買って、多項式から勉強やってるんですが
まぁ、ﾏｯﾀﾘいきたいと思います。

2年以内には作りあげたいです。

age

>>368
「セルオートマトン」なら11900件ヒットするよ
「セルラーオートマトン」は1340件。
前者でもう一度探してみたら？

>>371さん
情報どうも、ありがとう。ｾﾙｵｰﾄﾏﾄﾝで、調べてみます

反復補題を満たすが正規言語ではない言語にはどのようなものがあるでしょうか？。

マトンて羊？

>>374
羊の肉

>>373
Aを正則表現a+(=aa*)で定義される正則言語、Bを正則言語でないとして
L=AB={αβ|α∈A,β∈B}
とすればLはそういう言語になりそうな気がする。

>>376
ありがとうございます。
L={a^nb^m|0<n≦m}
っていうのもそうですね。

【分散処理】またーりdistributed.net【懸賞有】
http://pc7.2ch.net/test/read.cgi/mac/1078473726/l50

245

781

>>378
落ちた

宣伝した直後でのdat落ちか。哀れ

793

533

【オートマトン】自動羊肉、つまり羊。
あたりまえのことをもってまわっていいたがる
ペダンティックな人が好む言い回し。

すると牛はオートビーフで鶏はオートチキン？

オートマトン＝オート・マ・トン＝高みの・わが・愚かさ

ブール代数でも双対原理があるけど、両者に何か相関性あるのかね。

三年二時間。

age

685

544

>>307
世のなかに実在する計算機はすべて有限オートマトンです。メモリって有限しかない。チューリングマシンじゃないから。

チューリングマシンは実在するんだあああっ
脳内にぃぃぃ

>>393
コンピュータ≒チューリングマシン
（セル）オートマトン≒ウェブ全体

オートマトンの研究って結局どんなところに行き着くの？

あとそれから、例えばia32プロセッサとメモリを一つのオートマトンとして
捉えるとしても、非同期で入ってくる割り込みみたいな事象は、オートマトンの
理論としてはどう考えるのがいいの？

いや、非同期で入ってくるものも、別にプロセッサが特殊な動作をするわけじゃなくて、
指定された割り込み処理用ルーチンに飛ぶだけだから、オートマトンの理論的になんの
問題もないんだけど、そういう外部から来るものは特別に考えたりするのかなーっと思って。

むしろそういう外部から来るものを遷移のラベルにするものだと思うが。

>>398
まだ、セルオートマトンの初歩的なことしか分らないです。
http://www001.upp.so-net.ne.jp/suzudo/index.html

これによって現実の計算機をどうやって考えたらいいのかなーって
思い巡らしてました。セルの全体を整列集合みたいに考えて、セル自身の
インデックスもパラメータとして受け取るような関数が定義できる、
そんなオートマトンがありえないかと適当に妄想してました。
集合論の初歩すらしらないド素人ですんません。
セルオートマトンのあまりにシンプルな考え方に感動したので。

>>399
最初から妄想飛ばしても長続きしないし仲間はできないよ。
まずはなんでもいいから専門書をみっちり読むこと。

>>400
にゃー、レスどもです。
有り余る時間だけが友達のヒキコモリなので、仲間はできなくてもいいけど、
妄想を廃してちゃんと考えるには、集合論をみっちりやらんとだめみたいっすね・・・

まずは

> どんなところに行き着くの？
> どう考えるのがいいの？

こういう表現で欲望をすべて満たそうという根性が直ったらまた来なさい。

age

質問いいですか？

age

すいません，質問なのですが，できれば答えてください．
いま，正則表現を簡易にしようとしたのですが，簡易にする方法が参考書のどこにも載っていません．
答えだけは載っていて，
a*+(a*ba*b)(b+aa*ba*b)*aa*が，(a*+ba*bb*a)*と変換できるみたいです．
何か便利な手続きがあるのでしょうか？それとも感で進めるのですか．
誰かお願いします．

>>406
答え見てから解法を作ったので今後役に立つかわからんが
まず任意の正規表現R,Sについて
(1) (R+S)* = R*(SR*)
(2) R(SR)*S = RS(RS)* →以下 (RS)# と略記。ε+(RS)# = (RS)* に注意。
であることを示しておく。
その上で
与式
= a*+(a*ba*b)b*((aa*ba*b)b*)*aa* …(1)
= a*+a*((ba*bb*)(aa*))# …(2)
= a*(ε+(ba*bb*aa*)#) …分配則
= a*(ba*bb*aa*)* …(2)の注意より
= (a+ba*bb*a)* …(1)
第1項がa*じゃなくてaになってるけど全体に*がかかるから実際には同じ。

(1)は
(R+S)* = R*(SR*)* に訂正

>>407,408
やっぱり感（というか経験）でやっていくのですね．
ありがとうございます．

機械つくってる会社ってオートマトンから考えて作っていくの？

ＡＣＭってよく出てくる会社名だけどどう読むの？

>>411
これのこと？
http://www.acm.org/

1

age

　　　数学は死んだ・・・。　　　

純粋数学は死んだ・・・。
今はコンピューティングの時代だ。

ということで、コンピューティングによる数学の統合。
その最前線を語るすれにすれ。

まあ、アメリカでは破竹の勢いだけど、日本ではマターリ
ルベーグ積分とかしてるんだもんな。オラオラ！世界は動いてんだ！

9

age

610

age

grepをはじめとする情報科学での応用について、このスレの人たちは知っているんだろうか？

>>420
おｋ。何が望みだ？

age

750

S -> 01A
A -> 0 | 1B
B -> 1 | 0A
と等価な左線形文法はどうなりますか？

409

質問！
プッシュダウンオートマトンを文脈自由文法に変換するとき、
たとえば、δ(q0,0,Z)={(q0,XZ)} から
[q0,Z,q0]-->0[q0,X,q0][q0,Z,q0]
[q0,Z,q0]-->0[q0,X,q1][q1,Z,q0]
を出したりするのは、あれはどういうことなのですか？
さっぱりわかりません。教えてください。

Sは開始記号、大文字は非終端記号、小文字は終端記号です。
S→aB | bA
A→a | aS | bbA
B→b | bS | aBB
をチョムスキーの標準形に書き換えます。

C→a, D→b, E→DA, F→BB, G→CS, H→DS
としたところ、
S→AB | E
A→C | G | DE
B→D | H | CF
となりました。

講義や書物には、右辺に開始記号以外の非終端記号が１つのものは
出てきません。これで正しいのでしょうか？

違いますね･･･。
新たに開始記号S_0を使い、

S_0→AB | E
A→C | CS | DE
B→D | DS | CF
S→AB | E
C→a
D→b
E→DA
F→BB
でしょうか？

これでも右辺に開始記号以外の非終端記号が１つのものが
含まれます。これは正しいのでしょうか？お願いします。

>427 >428
どちらも違うと思います（右辺に変数が１つだけの規則があるので）。
以下が正解の一つかな。
S→CB | DA
C→a
D→b
A→a | ES | DF
E → a
F → DA
B → b | DS | CG
G → BB

>426は分からん。

>>429
レスありがとうございます。
かなりの過疎だったのでレスがいただけて驚いています。
F → DA があり、Sの右辺に DA がありますが、
規則を守るために F に置換はしないのですね。

おそらく　E → a は冗長であると思います。

>>428で新しく開始記号 S_0 を置きましたが、これはチョムスキー標準形に変換する前の
自由文法のときに S→ε が含まれているときのみにすることなのですね。
疑問が解消され、理解が深まりました。ありがとうございました。

>おそらく　E → a は冗長であると思います。
そうですね。

オートマトンをラベルとするようなオートマトンを考えました。
今特許申請中です。

右線形規則 A→aB と等価な左線形規則は B→Aa ですよね？
書物を何冊か見てみましたが、全部こう書いていました。

しかし、うちの教授は A→Ba と言っていました。
講義内で扱った例題でも、教授が言ったやりかたで左線形規則に書き換えています。
うちの教授間違ってますよね？

>>432
オートマトンをラベルとするようなオートマトンをラベルとするオートマトンを考えました
いま特許申請中です。

287

229

四年。

age

718

入門書プリーズ

工学系でも良い？

288

初期状態にεの入る遷移表の書き方がよく解りません。
ε-NFAというのでしょうか、非決定⇔決定のモノです。
初期状態でないモノなら、
б( б(q1,a) ,ε) = q2 としてしまえば良いのは解るのですが、
先に
　　　ε
p0　{ b,c }と与えられていた場合には
ε遷移を行ったモノを初期状態として書いていけばよいのでしょうか？
乱文ですが、どなたかお願いします。

814

480

270

860

すいません。>>163で紹介されている「計算理論の基礎」なんですけど、この本でＨｉｌｂｅｒｔの第10問題
は解かれているんでしょうか。ざっと立ち読みしただけではわからなんだ。Ｈｉｌｂｅｒｔの第10問題を解決するための
基礎となる技法を開発する、なんてフレーズは見つけたんですが、解決するところまで説明してくれてるのか
どうかがわからなんだ。もし解かれているなら購入しようと思ってます。どなたか親切な方教えて著。

すいませんageます

315

質問なんですが
決定性有限オートマトンで

0と1からなる文字列で前半と後半の文字列が同じで文字列の文字数は偶数、
つまり、受理するのはwwでwは0,1からなる文字列を受理する
オートマトンの遷移規則や解説を教えてください、お願いします。

×質問なんですが
○宿題の丸投げなんですが

301

>>443
http://www.amazon.co.jp/gp/product/4781910262/503-6823398-6921508?v=glance&n=465392

工学系の本らしいが、記述は数学的にしっかりしている。

>>454
可能なのか？スタック付けないと無理な気がするが。

359

五年二時間。

http://www.amazon.co.jp/gp/product/433901821X/

これってどうなの？

>>454

そんな有限オートマトンは存在しない

何か話題はないの？

性器表現＝有限オートマンコ

>>432ＤＦＡ（決定性オートマトン）なのでreject
>>434「オートマトンをラベルとするようなオートマトン」は「オートマトン」なので
「オートマトンをラベルとするようなオートマトンをラベルとするようなオートマトン」は即ち
「オートマトンをラベルとするようなオートマトン」でありそれは既に>>432で発明されているのでreject
>>406
a*+(a*ba*b)(b+aa*ba*b)*aa*
=a*+a*ba*b(b+aa*ba*b)*aa*
　　ここで (b+aa*ba*b)* = (b*+aa*ba*b)* であり、これはイコール b*(aa*ba*bb*)* であるので、
=a*+a*ba*bb*(aa*ba*bb*)*aa*
　　またカッコの後ろの aa* をカッコの中に入れ、カッコの先頭の aa* を前に出す。
=a*+a*ba*bb*aa*(ba*bb*aa*)*
　　先頭のa*をまとめる。
=a*{ba*bb*aa*(ba*bb*aa*)*}?
　　中カッコの中は ba*bb*aa* の一回以上の繰り返しであるが、
　　それに ? が付くのでゼロ回以上の繰り返しを意味している。
=a*(ba*bb*aa*)*
　　x*(yx*)* の形は (x*+y)* に変換可能なので、x=a,y=ba*bb*a として
=(a*+ba*bb*a)*
となる。
ちなみに、ＮＦＡエンジンの正規表現ルーチンに喰わせるには a*(ba*bb*aa*)* の形が最高効率。

118

ポンピング補題で正規じゃないのというのは話はわかるんだが、逆に正規であることを示すときのポイントって何？

教えてエロイ人

>>15
どちらかの道（どちらでも良い）を指差し、どちらかの相手（どちらでも良い）に
話しかける：
「あなたは、『この道が天国への道ですか』と聞かれたら『はい』と答えますか？」


話しかけた相手で場合分け：
1.天使の場合→信頼できる．
2.悪魔の場合．指差した道で場合分けする．
2a. 天国への道の場合．うそつきだから『』内の質問には「いいえ」と答えるはずだが、《『』内の質問に「いいえ」と答える》という真実を述べられない悪魔は「はい」と答える．
2b. 地獄への道の場合．うそつきだから『』内の質問には「はい」と答えるはずだが、《『』内の質問に「はい」と答える》という真実を述べられない悪魔は「いいえ」と答える．

同様の回答変種多数あり．悪魔が二重否定で真実を述べるのがポイントかと．
君が死んだら活用してくれたまえ．

それから、もし間違ってたらごめん．

607