うさぎでもわかるオートマトンと言語理論 第03羽 オートマトンの演算（前編）
(1) \( M_1 \) を決定性オートマトンに直しなさい。[前回の復習](2) \( \Sigma^ - L(M_1) \) を受理するような決定性オートマトンを書きなさい。(3) \( L(M_1) \cup L(M_2) \) を受理するような決定性オートマトンを書きなさい。(4) \( L(M_1) \cap L(M_2) \) を受理するような決定性オートマトンを書きなさい。(5) \( L(M_2) - L(M_1) \) を受理するような決定性オートマトンを書きなさい。
練習2(1) 言語 \( L_1 \cup L_2 \) が正則ならば、当然 \( L_1 \), \( L_2 \) ともに必ず正則である。(2) 言語 \( L_1 \cap L_2 \) が正則ならば、当然 \( L_1 \), \( L_2 \) ともに必ず正則である。(3) 言語 \( L_1 \), \( L_1 \cup L_2 \) が正則ではないのに \( L_2 \) が正則となる場合が存在する。(4) 言語 \( \Sigma^ - L \) が正則ならば、当然 \( L \) は必ず正則である。(5) 言語 \( L_1 \), \( L_2 \) がともに正則でないならば、当然 \( L_1 - L_2 \) は正則でない。(6) 言語 \( L_1 \), \( L_2 \) がともに正則でないならば、当然 \( L_1 \cap L_2 \) は正則でない。(7) 言語 \( L_1 \), \( L_2 \) がともに正則でないならば、当然 \( L_1 \cup L_2 \) は正則でない。(8) 言語 \( \overline \) が正則でないならば、当然 \( L \) も正則ではない。(9) 言語 \( L_1 \cup L_2 \) が正則でないならば、\( L_1 \), \( L_2 \) のうち少なくとも一方は正則ではない。(10) 言語 \( L_1 \cap L_2 \) が正則でないならば、\( L_1 \), \( L_2 \) のうち少なくとも一方は正則ではない。
５．練習問題の答え
解答1\( \Sigma^ - L(M_1) = \overline \) となるので、\( L(M_1) \) の補集合を受理するようなオートマトンを書けばOK。補集合は決定性オートマトンの受理状態と非受理状態を入れ替えるだけ。よって下のように書ける。
まずは、\( L(M_1) \) と \( L(M_2) \) の状態遷移表を書き、同時に読んでいった状態遷移表を新たに書く。
（左側の数値が \( L(M_1) \) の状態、右側の数値が \( L(M_2) \) の状態を表す。）
\( L(M_1) \cup L(M_2) \) なので（和演算）、どちらか片方でも受理状態であれば \( L(M_1) \cup L(M_2) \) においても受理状態となる。
\( L(M_1) \cap L(M_2) \) なので（積演算）、両方が受理状態であれば \( L(M_1) \cap L(M_2) \) においても受理状態となる。
\( L(M_2) - L(M_1) \) なので（差演算）、\( L(M_2) \) が受理して \( L(M_1) \) が受理しないような状態が \( L(M_2) - L(M_1) \) においても受理状態となる。（順番要注意！！）
解答2このような問題では \( \varepsilon \)（すべての文字を受理しないような言語）や \( \Sigma^ \)（すべての文字を受理するような言語）を例として考えるとかなり簡単に反例を考えることができます（\( \Sigma^ \) と \( \varepsilon \) は両方とも正則です）*2。
正則でない言語を \( N \) とおく。
解答：×理由：例えば、\( L_1 = N \), \( L_2 = \overline \) のとき、\( L_1 \cup L_2 = \Sigma^ \) となる。\( \Sigma^ \) が正則なのにも関わらず、 \( L_1 \), \( L_2 \) は正則な言語ではないのでこれが反例となる。
理由：例えば、\( L_1 = N \), \( L_2 = \overline \) のとき、\( L_1 \cup L_2 =\varepsilon \) となる。\( \varepsilon \) が正則なのにも関わらず、 \( L_1 \), \( L_2 \) は正則な言語ではないのでこれが反例となる。
理由：例えば、\( L_1 = N \), \( L_2 = \varepsilon \) とすると、\( L_1 \cup L_2 = N \) となり、\( L_1 \), \( L_1 \cup L_2 \) が正則ではないのに \( L_2 \) が正則となる。
理由：\( \Sigma^ - L \) は \( L \) の補集合を表している。
\( \overline \) の補集合は \( \overline = L \) となる。正則な言語の補集合は正則なので○。
\( L_1 = L_2 = N \) とすると、\( L_1 - L_2 = \varepsilon \) となり、\( L_1 \), \( L_2 \) が正則でないのに正則になってしまう。
ほぼ(5)と同じ。\( L_1 =N \), \( L_2 = \bar \) とすると、\( L_1 \cap L_2 = \varepsilon \) となり、\( L_1 \), \( L_2 \) が正則でないのに正則になってしまう。
\( L_1 =N \), \( L_2 = \overline \) とすると、\( L_1 \cup L_2 = \Sigma^ \) となり、\( L_1 \), \( L_2 \) が正則でないのに正則になってしまう。
対偶を取ると「\( L \) が正則ならば \( \overline \) も正則」となり、定義そのものになる。対偶が○なので元も○。
対偶を取ると「\( L_1 \), \( L_2 \) がともに正則ならば \( L_1 \cup L_2 \) も正則である」となり、定義そのものになる。対偶が○なので元も○。
対偶を取ると「\( L_1 \), \( L_2 \) がともに正則ならば \( L_1 \cap L_2 \) も正則である」となり、定義そのものになる。対偶が○なので元も○。
\( N \cup \overline = \Sigma^ \)、\( N \cap \overline = \varepsilon \) は典型的な反例として使いまくれるのでぜひ頭に入れておきましょう。
６．さいごに
*2 : 例えば「言語 \( L_1 \), \( L_2 \) がともに正則でないならば、当然 \( L_1 \cap L_2 \) は正則でない」の反例を見つけるのであれば、\( L_1 \) と \( L_2 \) が正則ではないのに \( L_1 \cap L_2 \) が正則となるようなものを1つでも見付ければよい。
公開日： 2019年9月2日 更新日： 2019年9月2日 この記事を書いた人 コメント一覧 コメントはありません。 関連記事 うさぎでもわかる配列と連結リスト うさぎでもわかる線形代数 第23羽 ジョルダン標準形を用いた行列のn乗の求め方 うさぎでもわかるε-δ論法・ε-N論法 うさぎでもわかる論理回路 - 順序回路の設計編 状態遷移図・状態遷移表の書き方 うさぎでもわかる2分探索木 後編 2分探索木における4つの走査方法 うさぎでもわかる論理回路 順序回路の読み方 うさぎでもわかる論理回路 Dフリップフロップを用いた順序回路の設計 【2021共通テスト】確率分布と統計的な推測 うさぎでもわかる解説 うさぎでもわかる線形代数 第18羽 対角化を用いた行列のn乗の求め方・行列の無限乗 うさぎでもわかる線形代数 第19羽 行列を用いた差分方程式（漸化式）の解き方カテゴリー
各種便利ツール・問い合わせ- 【完全無料】離散数学演習ツール・計算機まとめ
- 【ハッセ図】上界/下界・最大元/最小元・極大元/極小元・上限(最小上界)/下限(最大下界) 判定ツール
- 【ハッセ図】述語論理（∀・∃）真偽判定ツール
- 【離散数学】べき集合 2^A・P(A) 自動計算＆全列挙ツール
- 【離散数学】真理値表 自動作成ツール（途中式あり）
- 【離散数学】集合の「∈・⊆」真偽チェッカー（答え合わせ用）
- 【離散数学テスト対策】真理値表の穴埋めガチ演習ツール
- 【離散数学テスト対策】集合の「∈・⊆」ガチ演習！ 弱点分析つき○×ドリル
目次
- １．補集合演算
- (1) 補集合演算 \( \overline \), \( A^C \), \( \Sigma^ - A \)
- 補集合演算における注意
- (2) 和演算 \( L_1 \cup L_2 \)
- (3) 積演算 \( L_1 \cap L_2 \)
- (4) 差演算 \( L_1 - L_2 \)
- 練習1
- 練習2
- 解答1
- 解答2
工業大学生ももやまのうさぎ塾 (Momousagi Academy)
コンピュータグラフィックス コンピュータビジョン- １．補集合演算
- (1) 補集合演算 \( \overline \), \( A^C \), \( \Sigma^ - A \)
- 補集合演算における注意
- (2) 和演算 \( L_1 \cup L_2 \)
- (3) 積演算 \( L_1 \cap L_2 \)
- (4) 差演算 \( L_1 - L_2 \)
- 練習1
- 練習2
- 解答1
- 解答2