الفرق بين القواعد العادية و CFG في توليد تاريخ الحساب و $ \ سيغما ^ * $

Question

أود أن أطلب الحد من الحدس لفهم الفرق بين CFG Class="Span Class=" Math-Container "> $ \ Sigma ^ * $ و Grammar Gream $ \ سيغما ^ * $ .. حصلت على الأمثلة هنا من Sipser. دع $ {cfg} $ الرجوع إلى اللغة التي تنشئ CFG معين $ \ Sigma ^ * $ ، ودع $ {rex} $ الرجوع إلى اللغة التي يولد التعبير العادي المعطى $ \ sigma ^ * $ < / span> (ومنذ ذلك لأنه لكل تعبير منتظم هناك قواعد نحوية منتظمة، يمكننا أيضا أن نقول أن القواعد العادية المكافئة تنشئ $ \ Sigma ^ * $ ).

من ما حصلت عليه، لدينا:

• $ {cfg} $ غير صالحة للحساس، كما أنه لا يمنع التعرف عليه. دع $ \ overline {a_ {tm}} $ الرجوع إلى اللغة التي tm $ M $ هل عدم قبول إدخال كلمة $ W $ . يمكننا تقليل $ \ overline {a_ {tm}} $ إلى $ {cfg} $ في كثير الحدود الوقت باستخدام تاريخ حساب. ينشئ الحد من CFG الذي يولد كل الكلمات الممكنة حيث: 1) الأحرف الأولى لا تتطابق مع $ W $ ، 2) الأحرف الأخيرة لا تتطابق مع قبول التكوينات، و 3) الأحرف لا تتطابق مع انتقالات صالحة من تكوينات $ M $ . وبالتالي، $ a_ {tm} $ لا يقبل $ W $ IFF ينشئ CFG $ \ Sigma ^ * $ (أي لا يوجد أي توافق تاريخ حساب). منذ خرائط التخفيض $ \ overline {a_ {tm}} $ إلى $ {cfg} $ ، و $ \ overline {a_ {tm}} $ لا تورينج التعرف عليها، $ {cfg} $ لا تتلقى التعرف عليه.

• $ {rex} $ $ \ Sigma ^ * $ . ومع ذلك، فإن مشكلة قبول أي لغة منتظمة $ r $ يمكن تخفيض كثير الحدود إلى اللغة $ All_ {rex} - f (r_m) $ ، حيث $ R_M $ هو TM يقرر $ r $ ، و $ f (r_m) $ هو تخفيض مماثل لحساب التطبيق كما هو موضح أعلاه. بمزيد من التفاصيل، $ f (r_m) $ هو القواعد العادية التي تنشئ جميع الكلمات الممكنة حيث 1) الأحرف الأولى لا تتطابق مع $ W $ ، 2) الأحرف الأخيرة لا تتطابق مع تكوينات رفض، و 3) الأحرف لا تتطابق مع انتقالات صالحة من $ r_m $ $ All_ {rex} - f (r_m) $ يتحقق إذا كان فارغا (مما يعني أن $ f ( R_M) $ يساوي $ \ sigma ^ * $ ). إذا كانت فارغة، فلا يوجد تواريخ حساب حسابية و $ w \ in r $ . (في Sipser، استخدم شيئا كهذا لإظهار اكتمال المجهولة ل $ All_ {rex} - f (r_m) $ )

أود أن أسأل:

من الأعلى، يمكن أن يؤدي كل من النحو العادي و CFG إلى إنشاء تاريخ حسابي ل TM، ويمكن كلاهما إنشاء $ \ sigma ^ * $ . ولكن ما هو مع القوة الأساسية لقواعد CFG التي تجعلها صالحة لتقليل $ \ overline {a_ {tm}} $ to $ الكل_ {CFG} $ ، ولكن ليس من الممكن $ \ overline {a_ {tm}} $ ليتم تقليلها إلى $ All_ {rex} - f (a_ {tm}) $ ؟ أعلم أنه لا يمكننا تقليل $ \ overline {a_ {tm}} $ to $ {rex} - f (a_ {TM}) $ منذ $ All_ {rex} - f (a_ {tm}) $ هو مرحول، بينما $ \ overline {a_ {tm}} $ لا يتغاضي التعرف على ... ولكن أود أن أفهم ذلك من حيث الفرق في توليد الطاقة بين النحاس والوساطة العادية عبر قواعدهم.

على سبيل المثال، من ما قرأته، تصريح CFG القواعد $ a \ ignarrow bc $ ، حيث $ B $ و $ C $ هي سلاسل من المتغيرات والمحطات. من ناحية أخرى، تسمح النحو العادية فقط بقواعد فقط في شكل

-Container "> $ a \ charnarrow ab $ ، حيث $ $ هو محطة. أود أن أسأل: لماذا تتضمن قواعد النموذج $ a \ rawrow bc $ إلى قواعد اللغة، ومنحه ما يكفي من توليد الطاقة بحيث يكون صالحا بالفعل للحد $ \ overline{A_ {TM}} $ إلى Grammar (أي إلى CFG).

Answer 1

ملخصك لإثبات غير مناسب غير دقيق. مواصفاتك $ \ overline {a_ {tm}} $ غير صحيح.

للحصول على معرض معقول للإثبات، راجع https://liacs.leidenuniv .nl / ~ hoogeboomhj / second / codingcomputations.pdf وخاصة بداية القسم 1 والقسم 3.

الحدس ليس من السهل أن ينقل، حيث أن الدليل غير تافه تماما. ولكن هنا هي الحقيقة الأساسية. دع $ v، W $ يكون تكايدين لآلة Turing. اكتب $ n (v) $ ليكون التكوين التالي لآلة Turing بعد خطوة واحدة من الحساب، إذا بدأت في التكوين $ v $ . تحديد اللغة

$$ l={v \ # w ^ r \ mid n (v) \ Ne w \}. $$

ثم الحقيقة الرئيسية هي أن $ L $ خالية من السياق. هذا يأخذ بعض الدليل؛ إثبات أن هذه خطوة رئيسية في الدليل. ومع ذلك، هذا هو الحل على سؤالك: $ l $ خالية من السياق ولكن غير منتظم. نتيجة لذلك، يمكننا تقليل مشكلة توقف المشكلة إلى $ {cfg} $ ولكن ليس إلى $ All_ {rex} $ .

لقد تخطيت خطوات كثيرة لتعطيك نظرة عامة على الفكرة الرئيسية. ستحتاج إلى قراءة الدليل الكامل لملء التفاصيل. أقترح أنك قرأت بعد ذلك وفهم الدليل، مع مراعاة هذا المنظور، ثم إعادة النظر في ما كتبته هنا. نأمل أن يساعدك في فهم سبب حدوث دليل على وجود لغات خالية من السياق ولكنه سيفشل لغات منتظمة.

Answer 2

الفرق بين النماذج ينبع، بشكل حدسي، من قدرة CFGS على عدد . أكثر دقة، CFGS قادرة على توليد سلاسل من النموذج $ a ^ nb ^ n $ ، حيث عدد $ a $ 's و $ B $ ' s هي نفسها.

هذه القدرة تمنحها القدرة على مقارنة السلاسل، والتي يمكن بعد ذلك استخدامها لإظهار غير مبرر، لأن CFG قادرة على مقارنة محتويات الشريط بين تكوينات متتالية.

يصبح هذا أكثر وضوحا إذا كنت تتذكر أن مشكلة وقف آلات ثنائية العداد (ماكينات Minsky) غير قابلة للتكرار. هناك، يتم تقديم التكوين من قبل قيم عدادين. يمكنك هذا من هذا ك TM مع نوع من Unary Alphabet (على الرغم من ليس بالضبط). في جهازين عدادين، مقارنة تكويناتين متتالية بكثير بمقارنة قيم العدادات في خطوات متتالية، والتي تصل إلى اليمين إلى CFGS.

في المقابل، يتم التقاط اللغات العادية بواسطة Automata State Finite، والتي لها ذاكرة محدودة، وقادرة على الاعتماد على رقم ثابت فقط. وبالتالي، يمكن لهذه الآلية محاكاة TM طالما أن طول التكوين يحد مقدما. لماذا هذا يعطينا صلابة pspace؟ حسنا، يمكنك محاكاة أي يعمل في المساحة المحددة، لا يجب أن يكون متعدد الحدود في الإدخال. ومع ذلك، من أجل التقليل من أن يكون متعدد الحدود، فأنت بحاجة إلى أن تكون متعدد الحدود. وبالتالي، تحصل على صلابة PSPACE بالضبط.

فيما يتعلق ب "نوع" القواعد، فهذا ليس كثيرا $ a \ to bc $ القواعد التي هي مشكلة، إنها أكثر في قواعد شكل $ aab $ (أو أكثر عموما، القدرة على الحصول على قواعد دوري ). السبب هو أن $ a \ to bc $ لديه بنية "الشجرة"، وإذا كان $ B $ و $ C $ غير مرتبطة لاحقا، ثم هذه عملية نقابية فعالة، والتي يمكن أن تحاكي اللغات العادية.

ومع ذلك، قاعدة من النموذج $ aab $ يحافظ على "السياق" $ $ ، وهو أمر لا يستطيع اللغات العادية القيام به.

لتلخيص:

semantically، تكمن قوة CFGS في قدرتها على الاعتماد.

سكل، قوة CFGS تكمن في قواعد دورية.