Σ = {1, +, -} E→ 1 | EE+ | E- Eを式（その定義は上の文法）として、 S→ E S→ SE P→ S | SEE+ SはEのシーケンスで、Pはプレフィックスから。Eの言語をL, Pの言語をL'として、ターゲット命題は L' = Prefix(L) M = Prefix(L) とすれば、 L'⊆M M⊆L' 2番目の証…

簡単な方法 合併： 正規表現の'|'があるので、それが合併 否定： DFAの終状態（受理状態）と非終状態（非受理状態）を入れ替える。NFAをDFAにする必要がある！ 共通部分： ド・モルガンの法則 集合差： L＼L' = L∩L'c 対称差： L△L' = (L＼L')∪(L'＼L) 直接…