غير العادية الخالية من السياق اللغة لانهائية العادية sublanguages

Question

كان لدي عمل جامعة الأساس الذي قال:

"يدل على أن غير العادية اللغة L={0^n 1^n :ن الطبيعي} أي لانهائية العادية sublanguages."

لقد أظهر هذا التناقض.لقد قال أساسا أن هناك لغة S وهو sublanguage من L و هو اللغة العادية.منذ الممكن التعابير العادية S 0*, 1*, (1+0)* و (0o1)*.لقد تحقق كل قواعد اللغة تثبت أن أيا منهم هي جزء من اللغة L.

ولكن كيف يمكن إثبات أن أي غير العادية السياق مجانا اللغة لا يمكن أن تحتوي على أي العادية لانهائية sublanguages?

أنا لا أريد أن أثبت في حد ذاتها ، أنا فقط أريد أن أكون وأشار في الاتجاه الصحيح.

Answer 1

L = {0^n 1^n :ن الطبيعي} غير العادية السياق مجانا.

M = 2*3* هو لانهائي العادية.

N = L∪م غير العادية السياق مجانا.ن على م

Answer 2

عن 0^n 1^ن اللغة ، فإنه قد يكون من المفيد أن ننظر إلى ضخ يما. أعتقد عندما علمت ضخ يما كان يستخدم على أ^ن ب^ن اللغة (نفس الشيء) ربما ضخ يما قد تساعد في دليل الخاص بك.

أيضا يمكنك أن تنظر في هذا العادية اللغات مغلقة تحت تكمل الاتحاد والتقاطع ، kleene نجوم.

هذا إذا L1 و L2 العادية ثم:

L1 L2 (concatenation) is also regular.
L1 n L2 is regular
L1 U L2 is regular
¬L1 is regular 
L1* is regular

فمن الممكن أن كنت يمكن أن تثبت أن أي لغة تحتوي على العادية لانهائية sublanguage العادية باستخدام بعض من هذه القواعد.

Answer 3

الغرائز الخاص بك جيدة.اثنين من الأشياء هنا.

أولا دائما تقريبا عند السؤال يأخذ شكل "عرض أنني غير العادية/لا انظر" الجواب هو الذهاب إلى إشراك باستخدام ضخ lemmas.وبالمثل, عندما تحصل على سؤال مثل "لا س أن ..." الطريق السهل هو (دائما تقريبا) ستكون البرهان بالتناقض.

Answer 4

تحرير:بيان كاذب, لا ينطبق إلا على السياق مجانا اللغة

Answer 5

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