هل هذا صحيح: ما إذا كان Grammar من النوع 3 يولد $ \ Sigma ^ * $ ليس C.E

Question

مثال من كتاب Sipser's، مقدمة في نظرية الحساب، يدل على أنه ليس منسقلا ل $ tm $ للتعرف على ما إذا كان $ CFG $ (أو grammar grammar) ينشئ $ \ sigma ^ * $ ، حيث $ \ سيغما $ هو الأبجدية. استدعاء هذه اللغة $ cfg_ {all} $

ولكن اللغة المذكورة أعلاه غير ثابتة أيضا. يمكن أن يكون هناك انخفاض من $ cfg_ {all} $ to $ \ bar {a_ {tm}} $ ، حيث $ \ bar {a_ {tm}} $ هو لغة اللغة المدخلات $ tm $ لا يقبل أي إدخال. $ \ bar {a_ {tm}} $ غير قابلly.

ولكن هل يمكن أن نقول أنه ما إذا كان جوهر النحو من النوع 3 ينشئ $ \ Sigma ^ * $ هو أيضا غير c.e. ؟ (نظرا لأن النحو من النوع 3 هي مجموعة فرعية من قواعد النحوية الخالية من السياق). في حين أنه صحيح أن Automaton Finite يمكن أن يتعرف على $ \ sigma ^ * $ ، هذه اللغة مختلفة مباشرة من ما إذا كان قواعد اللغة الثالثة ينشئ $ \ Sigma ^ * $ ؟

فقط لتوضيح مصدر الارتباك الخاص بي، باختصار، من القراد ل $ TM $ لتحديد ما إذا كان Automaton Pushnation يتعرف على $ \ Sigma ^ * $ أو يقبل أي إدخال، لكنه غير قابل للاستحقاق أو حتى عددا غير قابل للتعدي للحصول على $ TM $ للتعرف على ذلك CFG يولد $ \ sigma ^ * $ . وبالمثل، فإنه رائعا ل $ tm $ للتحقق مما إذا كان Automaton Finite يقبل $ \ Sigma ^ * $ ، ولكن قد لا يكون منقسما ل $ tm $ للتحقق مما إذا كان قواعد اللغة الثالثة ينشئ $ \ Sigma ^ * $ . إنه فرق بطريقة أو بأخرى بين الاعتراف والتوليد.

تحرير: على ما يبدو بالنسبة لبرنامج Automaton Pushnated للتعرف على $ \ Sigma ^ * $ غير قابل للحساس

Answer 1

لمعرفة ما إذا كان Grammar Grammar (منتظم) ينشئ $ \ Sigma ^ * $ فقط قم ببناء الحد الأدنى من DFA قبول اللغة، والتحقق مما إذا كان ذلك الأول= الحالة النهائية، مع حلقة على جميع الرموز.جميع المنشآت المعنية فعالة.