الحوسبة Automaton مقابل $ l (a) / l (b) $ يعطي منها مقابل $ A، B $

Question

أحاول معرفة ما إذا كانت اللغة اللانهائية تتغير الإجابة.

إظهار

أن اللغة التالية صالحة للغاية: $$ l={\ langle a، b \ rangle: \ text {$ a، b $ هي dfas، $ l $ هو محدود، $ l (a) / l (b)= l (0 ^ * 1 ^ *) $} \}. $$

(أنا أتحدث عن الانقسام الصحيح.)

نحن نعرف كيفية التحقق مما إذا كانت لغة DFA محدودة، وحددت اثنين من DFAS، ونحن نعرف كيفية التحقق مما إذا كانت لغاتها متساوية. تستخدم الخوارزميات التي أعرفها للمشاكل المذكورة أعلاه DFA، لذلك من الضروري وجود DFA من أجل تحديد هذه المشاكل.

أحاول معرفة ما إذا كان $ | l (b) |=enfty $ يغير الجواب. إلى أفضل فهمي، لأن $ | l (b) | <\ infty $ ، يمكننا إنشاء DFA صراحة التي تقبل $ l (a) / l (b) $ ، في حين إذا $ l (b)=infty $ كل ما نعرفه هو عن الوجود من $ DFA $ يقبل $ l (a) / l (b) $ .

ومع ذلك، حتى لو $ l $ هي لغة لا حصر لها، حيث يوجد عدد محدود من DFAS، أحدها يقبل $ l (a) / l (b) $ ، بالتأكيد أستطيع أن أعرف أن هناك آلة turing تقرر اللغة $ l $ . أليس كذلك؟

Answer 1

ما الذي تطرحه حقا هو ما إذا كان إعطائه تلقائيا $ a، b $ ، يمكننا إنشاء شركة Automaton التي تكون لغتها هي الحاصل الأيسر $$ l (a) \ backslash l (b)={w: \ \ exist x \ in \ sigma ^ * \ text {s.t. } x \ in l (a) \ text {and} xw \ in l (b) \}. $ (لقد تغير السؤال في الوقت نفسه للإشارة إلى الحاصل الصحيح، والتي يمكن معالجتها بالمثل.)

هنا هو مثل هذا البناء. افترض أن $ A، $ $ هي DFAS مع الدول $ q_a، q_b $ ، والدول الأولية $ {0a}، q_ {0B} $ ، وظائف الانتقال $ \ delta_a، \ delta_b $ ، والدول النهائية $ f_a، f_b $ . نحن نبني NFA مع الدول $ q= (\ {0 \} \ times q_a \ times q_b) \ cup (\ {1 \} \ times q_b) $ ، الحالة الأولية $ \ lovern 0، q_ {0a}، q_ {0B} \ rangle $ ، والدول النهائية $ \ {1 \} \ Times F_B $ ، وظيفة الانتقال التالية $ \ Delta $ :

• $ \ delta (\ lovery 0، q_a، q_b \ rangle، \ epsilon)={\ langle 0، \ delta_a (q_a، \ sigma)، \ delta_b (q_b ، \ Sigma) \ Sigma) \ Sigma \ at \ sigma \} $ لجميع $ q_a \ in q_a \ setminus f_a $ and $ q_b \ in Q_B $ .
• $ \ delta (\ lovery 0، q_a، q_b \ rangle، \ epsilon)={\ langle 0، \ delta_a (q_a، \ sigma)، \ delta_b (q_b ، \ sigma) \ sigma) \ sigma \ sigma \ in \ sigma \} \ cup \ {\ langle 1، q_b \ rangle \} $ لجميع $ q_a \ in f_a $ و $ q_b \ in Q_B $ .
• $ \ delta (\ lange 1، q_b \ grocle، \ sigma)={\ {\ lovero 1، \ delta_b (q_b، \ sigma) \ rangle \} $ لجميع $ \ sigma \ in \ sigma $ $ q_b \ in q_b $ .

Answer 2

هذا يجيب على نسخة مختلفة من السؤال، حيث تكون اللغة المعنية $ l (a) \ setminus l (b) $ .

هنا خوارزمية لتحديد $ l $ :

• استخدم بناء المنتج لبناء DFA $ c $ التي هي لغتها $ l (a) \ setminus l ( ب) $ .
• دع $ D $ تكون DFA لغتها هي $ 0 ^ * 1 ^ * $ . < / لى>
• استخدام بناء المنتج مرة أخرى لبناء DFA $ e $ له لغة $ l (c) \ delta l (د) $ .
• تحقق (باستخدام BFS / DFS) ما إذا كانت بعض الحالة النهائية من $ E $ يمكن الوصول إليها من حالتها الأولية.
• إخراج "نعم" إذا لم يتم الوصول إلى حالة نهائية من الحالة الأولية. إخراج خلاف ذلك "لا".

كما ترون، ما إذا كانت اللغات التي تواجهها على طول الطريق هي محدودة أو لا حصر لها فرق على الإطلاق لهذه الخوارزمية.