このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

正規言語のブール演算とか操作とか

簡単な方法

  1. 合併: 正規表現の'|'があるので、それが合併
  2. 否定: DFAの終状態(受理状態)と非終状態(非受理状態)を入れ替える。NFAをDFAにする必要がある!
  3. 共通部分: ド・モルガンの法則
  4. 集合差: L\L' = L∩L'c
  5. 対称差: L△L' = (L\L')∪(L'\L)

直接的

  1. 合併: 2つの開始状態をεでつないで、ε除去手順を使う。非可達ノードを消す。
  2. 否定: DFAにする。
  3. 共通部分: 状態空間は積P×Qにして、遷移関係をS, Tとするとき、新しい遷移関係Uを次のように定義する: ( (p, q), a, (p', q') )∈U ⇔ (p, a, p')∈S, (q, a, q')∈T。