スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

開始。そしてオートマトン

こんばん。
とはいえど、一日目から書くことが特にありませぬ。

今、勉強している内容はPostの対応問題の非可解性です。
すでに非可解であることが証明されている問題Qを、非可解性を証明したい問題Pに還元することができれば、非可解であることは理解しているのですが、何せ還元についてうまく理解できない。
どうにかしてわかりやすい情報を得ることはできんもんかのぅ・・・。

本日理解した内容は言語L1を認識する決定性有限オートマトンM1と言語L2を認識する決定性有限オートマトンM1の直積オートマトンを構成したとして、L1-L2の差集合を認識するオートマトンにするためにはどのように初期状態と受理状態を設定すればよいかと言う話。

これについては各オートマトンによって認識される言語の集合L1とL2をわかりやすいものとすれば理解しやすいと思われる。
詳細については今回は述べないが、例えば

L1:列の長さが3の倍数であるような言語
L2:1を少なくともひとつは含むような言語

このような言語と設定すれば、この差集合L1-L2は

L1-L2:列の長さが3の倍数であり、0のみで構成された言語

を認識するような直積オートマトンが構成できればよいとわかる。
このようにするために、初期状態と受理状態をどのように設定すればよいかは自然とわかってくるのではないだろうか。
図を用いた説明は、後日また書くかもしれない
スポンサーサイト
プロフィール

朔夜だったり、シェルジュだったり

Author:朔夜だったり、シェルジュだったり
FC2ブログへようこそ!

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
カウンター
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。