正規言語のブール演算とか操作とか
簡単な方法
- 合併: 正規表現の'|'があるので、それが合併
- 否定: DFAの終状態(受理状態)と非終状態(非受理状態)を入れ替える。NFAをDFAにする必要がある!
- 共通部分: ド・モルガンの法則
- 集合差: L\L' = L∩L'c
- 対称差: L△L' = (L\L')∪(L'\L)
直接的
- 合併: 2つの開始状態をεでつないで、ε除去手順を使う。非可達ノードを消す。
- 否定: DFAにする。
- 共通部分: 状態空間は積P×Qにして、遷移関係をS, Tとするとき、新しい遷移関係Uを次のように定義する: ( (p, q), a, (p', q') )∈U ⇔ (p, a, p')∈S, (q, a, q')∈T。