إغلاق اللغات العادية

Question

a) دع $ L $ كن لغة منتظمة.وفقا لنظرية هناك DFA يقبل اللغة.

صف قريبا كيفية تغيير DFA إلى NFA الذي يقبل $ l $ ^ r $ ، حيث R قيد التشغيل.

ليست هناك حاجة لكتابة كيفية البناء رسميا أو إثبات أو صحة.

b) صحيح أو خطأ: إذا كان $ L $ غير منتظم ثم $ l ^ r $ ليس منتظم

حلاي:

a) أولا وقبل كل شيء لأننا نريد عكس حالة القبول ستصبح البداية، وسوف تصبح الدول الرفانية قبولها، وتغيير أيضا اتجاه الحواف إلى جانب المنافس. ولكن عندما يتعلق الأمر بتغييرها إلى NFA أنا عالقة بعض الشيء.

b) أعتقد أنه صحيح لأنه لا يهم إذا عكس إذا كان منتظم ثم بالطبع $ l ^ r $ سيكون منتظما أيضا.

هل هذه هي الطريق ل A و B؟

Answer 1

a)

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

أنت هناك تقريبا. ماذا يحدث إذا كان لديك عدة دول مقبول في DFA الأصلية؟ هذا حيث تحتاج إلى قدرات NFA لتحويلها.

هنا هو المفسد في حال كنت ترغب في التحقق من إجابتك: تصميم DFA وعكسها على الكمبيوتر .

b)

إجابتك صحيحة على الرغم من أنك قد ترغب في عبارة ذلك بعناية أكثر بكثير. نريد أن نثبت "إذا $ l $ غير منتظم، $ l ^ r $ غير منتظم" وبعد لذلك دع $ l $ لا تكون منتظمة. إذا $ l ^ r $ كانت منتظمة، لذلك كانت $ (l ^ r) ^ r= l $ ، وهو أمر تناقض. وبالتالي، $ l ^ r $ غير منتظم.