$ 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의 언어가 유한 여부를 확인하는 방법을 알고 있으며 두 개의 DFA가 주어지면 언어가 동일한 지 여부를 확인하는 방법을 알고 있습니다. 위의 문제에 대해 알고있는 알고리즘은 DFA를 사용하므로 이러한 문제를 결정하기 위해 DFA가 필요합니다.

$ | l (b) |=infty $ 답변을 변경하려고합니다. $ | l (b) | <\ infty $ 을 사용하기 때문에 $ L (a) / l (b) $ , $ l (b)=infty $ 우리가 알고있는 것은 존재에 관한 것입니다. $ DFA $ > $ L (a) / l (b) $

그러나 $ l (b) $ 이 무한한 언어이므로 유한 수의 DFA가 있기 때문에 $ l (a) / l (b) $ , 언어 $ l $ 오른쪽?

Answer 1

실제로 묻는 일은 Automata $ a, b $ 의 경우 언어가 왼쪽 지수 인 오토 마톤을 구성 할 수 있습니다 $$ l (a) \ backslash l (b)={W : \ in \ sigma ^ * \ text {s.t. } x \ l (a) \ text {and} xw \ in l (b) \}. $$ (한편은 마찬가지로 처리 할 수있는 적절한 몫을 참조로 변경 한 다음 질문이 있습니다.)

여기는 이러한 구성입니다. $ a, b $ 은 $ q_a, q_b $ , 초기 상태 $ Q_ {0A}, Q_ {0b} $ , 전환 함수 $ \ delta_a, \ delta_b $ 및 최종 상태 $ F_A, F_B $ . 우리는 $ q= (\ {0 \ \ times q_a \ times q_b) \ 컵 (\ {1 \ times q_b) $ q= (\ {1 \ time q_b) $ 을 구성합니다. 초기 상태 $ \ langle 0, q_ {0a}, Q_ {0b} \ rangle $ , 최종 상태 $ \ {1 \} \ times f_b $ 및 다음 전환 기능 $ \ 델타 $ :

• $ \ Δ (\ langle 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 \ in q_a \ setminus f_a $ 및 $ Q_B \ Q_B $ .
• $ \ Δ (\ langle 0, q_a, q_b \ rangle, \ epsilon)={\ langle 0, \ delta_a (q_a, \ sigma), \ delta_b (q_b , \ sigma) \ rangle : \ sigma \ \ \ sigma \} \ \ {\ langle 1, q_b \ rangle \} $ \ span 클래스="수학 컨테이너에 대한 $ $ q_a \ f_a $ 및 $ q_b \ q_b $ .
• $ \ Δ (\ langle 1, q_b \ rangle, \ sigma)={\ langle 1, \ delta_b (q_b, \ sigma) \ rangle \} $ 모든 $ \ sigma \ \ sigma $ 및 $ q_b \ q_b $

Answer 2

문제의 언어가 $ l (a) \ setminus l (b) $

이라는 질문의 다른 버전의 질문에 답합니다.

여기에 $ l $ :

를 결정하기위한 알고리즘입니다.

• DFA $ C $ 의 언어가있는 DFA $ L (A) \ SETMINUS L ( b) $
• $ d $ 언어가 $ 0 ^ * 1 ^ * $ 인 DFA가되도록하자. < / li>
• 제품 구성을 다시 사용하여 DFA $ e $ 을 구성하는 언어가 $ l (c) \ 델타 L (d) $ .
• BFS / DFS를 사용하여 $ e $ 의 일부가 초기 상태에서 도달 할 수 있는지 여부.
• 출력 초기 상태에서 최종 상태가 도달 할 수없는 경우 "예". 그렇지 않으면 "아니오"를 출력합니다.

보시다시피 언어가 발생했는지 여부는 유한 또는 무한대이 알고리즘에 대해 절대적으로 차이가 없습니다.