プログラミングのお題スレ Part17

[過去ﾛｸﾞ] プログラミングのお題スレ Part17 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

943: 2020/07/11(土)11:56 ID:8xOOoQBu(1/2) AAS
自作チューリングマシンを Pythonの改行15回程度で作れって？神だわ

944: 2020/07/11(土)11:57 ID:60oNEnIZ(3/6) AAS
動作を規定すればよくて
実際に動く機械を作る必要はない

945: 2020/07/11(土)11:59 ID:60oNEnIZ(4/6) AAS
と思ったが
Pythonでエミュレーターを作れって事か？

946(1): 2020/07/11(土)12:00 ID:60oNEnIZ(5/6) AAS
別に無限にメモリがある必要は無いけど
実際に動くどんなプログラムにも限界がある

947(1): 2020/07/11(土)12:01 ID:KPNFpi8s(3/4) AAS
>>946
メモリが有限だったらチューリングマシンとはいいましぇん＞＜

948: 2020/07/11(土)12:01 ID:2Qc0/uE/(1/2) AAS
適当な言語で状態遷移機械つくればええんちゃう

949: 2020/07/11(土)12:02 ID:8xOOoQBu(2/2) AAS
しかもCSVパーサーって
つまりはPython15行でExcelを再現しろと？

951(2): 2020/07/11(土)12:46 ID:6CWHpJ6z(2/2) AAS
>>938 Perl 状態セル4個
$ cat input
"aa,a",aa,,"aa\"aa"
$ perl odai938 < input
[None, 'a', 'a', ',', 'a', None, 'X', 'a', 'a', 'X', 'X', None, 'a', 'a', None, '"', 'a', 'a', None]
$ cat odai938

%maton = (
'N' => { 'a' => ['N', q('a')] , ',' => ['N', q('X')] , '"' => ['Q', q(None)] , '\\' => ['E', q(None)] },
'Q' => { 'a' => ['Q', q('a')] , ',' => ['Q', q(',')] , '"' => ['N', q(None)] , '\\' => ['F', q(None)] },
'E' => { 'a' => ['N', q('a')] , ',' => ['N', q(',')] , '"' => ['N', q('"') ] , '\\' => ['N', q(None)] },
省11

952: 2020/07/11(土)13:08 ID:WonOAWfv(1) AAS
チューリングマシンわからんけどめっちゃ面白そう

953: 2020/07/11(土)13:14 ID:JFnadz6+(1/2) AAS
オートマトンを使ってってことなのね、なるほど

954(1): 2020/07/11(土)13:56 ID:R3MTOjCq(1/4) AAS
>>951
チューリングマシンを使っていないのでだめだ
そのオートマトンは文脈依存文法どころか文脈自由文法すら対応していない
これら全てに対応出来てこそチューリングマシンだ
（このことは将来エラーリカバリーを考える上で、重要になると思っている）
つまりテープヘッドは左右に動き状態関数でそれを指示出来る(文脈自由文法に対応)
チューリングマシンは受理状態を指定出来る

今回、状態の数は受理状態を省略して５個でいける（もっと少なく出来るかもしれんが）
状態関数は状態５*記号４のマトリックスを考えて、その中の１２個を埋めればいい

955: 2020/07/11(土)16:08 ID:R3MTOjCq(2/4) AAS
訂正
×状態関数
◯状態遷移関数

956: 2020/07/11(土)16:29 ID:2Qc0/uE/(2/2) AAS
>>954が正解を出してくれるんだそうだ

957: 2020/07/11(土)16:36 ID:rnrtUK1e(1) AAS
例を出してくれ

958(1): 2020/07/11(土)17:01 ID:KPNFpi8s(4/4) AAS
そもそも作問の時点でおかしいんだよ！

959: 2020/07/11(土)17:09 ID:R3MTOjCq(3/4) AAS
>>958
どこがおかしい？
線形有界オートマトンといえば納得するか？
そんな言葉使わなくても実装出来る
と言うかこのスレにこの言葉知ってる奴いないだろ

960(1): 2020/07/11(土)17:49 ID:3Cd1PF49(1) AAS
焉んぞ牛刀を用いん

961(1): 2020/07/11(土)17:53 ID:60oNEnIZ(6/6) AAS
チューリングマシンの設計じゃなくて
チューリングマシンエミュレーターの設計だよな

962: 2020/07/11(土)18:17 ID:R3MTOjCq(4/4) AAS
>>951
\aやらを認めてるのが気になるがそれを直したら遷移関数はあってるな
後はチューリングマシンとして完成させるだけ
俺の遷移関数に冗長があったから直したら一致した
>>960
HTMLは文脈自由文法だが
WebKitのHTMLパーサーは非文脈自由文法として実装されている
そこでチューリングマシンが有用かはさせおき、非文脈自由文法を考えるキッカケになることもある思う
>>961
エンドマーカーを省略した線形有界オートマトンの実装な

上下前次 1-新書関写板覧索設栞歴

あと 40 ﾚｽあります
ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.028s