Loading...

非決定性有限オートマトンは、決定性オートマトンにできるらしい。

よくわかってないけど、とりあえずメモ
(1)非決定性により、有限オートマトンの計算能力は向上しない。
(2)非決定性有限オートマトンの方が設計が容易。
※(1)非決定性オートマトンで実行できることは決定性オートマトンでも実行できる。


非決定性オートマトンで設計して、あとで決定性オートマトンにする。



参考
計算論への入門―オートマトン・言語理論・チューリング機械 (スタンダードテキスト)
エフィーム キンバー カール スミス Efim Kinber
489471437X
リアクション: 
オートマトン 1318749296374128069

コメントを投稿

ホーム item

このブログを検索

Random Posts

Popular Posts

Labels

ADS