読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

「はじめて学ぶオートマトンと言語理論」読んだ

神山町に行ったとき状態遷移の話になり、オートマトンの基礎は知っておきたいと思ったので一番薄くてわかりやすそうなこの本を読んでみました。

はじめて学ぶオートマトンと言語理論

はじめて学ぶオートマトンと言語理論

一番興味があったNFA→DFA変換と受理はSchemeで実装しました。空遷移を含むNFAからの変換・等価性の判定・最簡形への変換・正規表現とNFAの相互変換・プッシュダウンオートマトンチューリングマシンの遷移は紙に書いて試して、残りの形式文法(正規文法・文脈自由文法)は今は興味が無いので流し読みしました。

なんとなくですが、空遷移を含むNFAからDFA最簡形までの変換や、文脈自由文法のチョムスキー標準形からグライバッハ標準形への変換が、Lisp-1処理系制作中に調べたlambdaの簡約や最適化を連想して興味深く思いました。もしかして何か関連があったりするんでしょうか?

1週間、1日1時間程度の取り組みでオートマトンに少しは親しむ事ができたので、特にCS系出身ではないプログラマの方におすすめします。ただグラフにいくつか間違いがあって、そこでかなり時間を取られたので注意してください。

広告を非表示にする