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

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