$ L（a）/ l（b）$のためのコンピューティングオートマトンは$ a、b $のためのものを与える

Question

無限の言語が答えを変えるかどうかを把握しようとしています。

次の言語が決定されたことを示します。 $$ l={\ langle a、b \ rangle：\ text {$ a、b $はdfas、$ l（b）$は有限、そして$ L（a） / l（b）= l（0 ^ * 1 ^ *）$} \} $$

（私は正しい部門について話しています。）

DFAの言語が有限であるかどうかを確認する方法を知っていて、2つのDFAを指定して、自分の言語が等しいかどうかを確認する方法を知っています。私が上記の問題を知っているアルゴリズムはDFAを使用するので、それらの問題を決定するためにDFAを持つ必要があります。

$ | l（b）|=infty $ を変更しようとしている。 $ | l（b）| <\ infty $ なので、 $ L（a）/ l（b）$ 、 $ L（b）=infty $ の場合、私たちが知っているのは存在についてのものです。 $ DFA $ の $ l（a）/ l（b）$ 。

しかし、 $ l（b）$ が無限の言語であっても、dfasの有限数は $ L（a）/ l（b）$ 、言語を決定するチューリングマシンがあることを確かに知っています $ l $ 。 右？

Answer 1

あなたが本当に尋ねているものを与えられたかどうかです、私たちはその言語が左の商であるオートマトンを構築することができます $$ l（a）\ backslash l（b）={w：\ exists x \ in \ sigma ^ * \ text {s.t。 l（a）\ text {および} xw} xw \ in l（b）\}。 $$ （質問は、同様に扱うことができる正しい商を指すように変更されたのです。）

こちらの構成です。 $ a、b $ が状態 $ q_a、q_b $ 、初期状態 $ Q_ {0a}、q_ {0b} $ 、遷移関数 $ \ delta_a、\ delta_b $ 、および最後の状態 $ f_a、f_b $ 。状態 $ Q=（\ {0 \} \ q_a q_b）\ cup（\ {1 \} \ times q_b）$ を持つNFAを構築します。初期状態 $ \ langle 0、q_ {0a}、q_ {0b} \ rangle $ 、最終状態 $ \ {1 \ \ revids f_b $ 、および次の遷移関数 $ \ delta $ ：

• $ \ delta（\ lange 0、q_a、q_b \ rangle、\ epsilon）={\ langle 0、\ delta_a（q_a、\ sigma）、\ delta_b（q_b \ sigma）\ rangle：\ sigma \ in \ sigma \} $ q_a \ setminus f_a $ および $ q_a \ "math-container"> $ q_b \ q_b $ 。
• $ \ delta（\ lange 0、q_a、q_b \ rangle、\ epsilon）={\ langle 0、\ delta_a（q_a、\ sigma）、\ delta_b（q_b \ Sigma）\ rangle：\ sigma \ in \ sigma \} \ cup \ {\ langle 1、q_b \ langle 1、q_b \ rangle \} $ f_a $ q_a \ in f_a $ と $ q_b \ q_b $ 。
• $ \ delta（\ \ \ delta（\ langle 1、q_b \ rangle、\ sigma）={\ langle 1、\ delta_b（q_b、\ sigma）\ rangle \} $}} $}}} SPAN>すべての $ \ sigma \ in \ sigma $ と $ q_b \ x x $ 。

Answer 2

これは、問題の言語が $ l（a）\ setminus l（b）$ です。

の異なるバージョンに答えます。

これは $ l $ を決定するためのアルゴリズムです。

• 製品構築を使用して、DFA $ C $ を作成します。この言語は、 $ L（a）\ setminus l（ b）$ 。
• $ d $ の言語が $ 0 ^ * 1 ^ * $ です。< / li>
• 製品構築を再度使用して、DFA $ E $ を作成します。 $ l（c）\ delta l （d）$ 。
• チェック（bfs / dfsを使用） $ e $ の最終状態は、初期状態から到達可能です。
• 初期状態から最終状態が到達できない場合は「はい」出力 "はい"出力。それ以外の場合は「いいえ」を出力します。

見ることができるように、途中で遭遇した言語が有限または無限であるかどうかはこのアルゴリズムの違いを絶対にしません。