هل هذه اللغة عادية أم لا؟

Question

لدي اللغة {4^(w⋅g)34^(g)|w,g∈NAT} فوق الأبجدية {0,1}.

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

كيف سأفعل ذلك أو أعرف؟

شكرًا

Answer 1

النظر في أي سلسلة من النموذج 4^a 3 4^b.هل يمكن أن نجد w, g لنا a, b؟حسنا، نحن نعرف ذلك g يجب أن يساوي b, ، وبعد ذلك يمكننا الاختيار w = a + g.منذ a, b و g هي أعداد طبيعية، لذا يجب أن تكون أيضًا w;الجواب هو نعم، لأي سلسلة من النموذج 4^a 3 4^b, ، لدينا سلسلة في لغتك.

لغة جميع سلاسل النموذج 4^a 3 4^b يتم وصفه بالتعبير العادي 4* 3 4* وعلى هذا النحو، تكون لغتك منتظمة وخالية من السياق وقابلة للتقرير ويمكن التعرف عليها.

لنفترض أن لغتك لم تكن منتظمة؛كيف استطعت القول؟يمكنك استخدام نظرية Myhill-Nerode أو Pumping Lemma للغات العادية لاشتقاق التناقض من افتراض أن اللغة عادية.

لنفترض أن لغتك لم تكن خالية من السياق.يمكنك استخدام Pumping Lemma للغات الخالية من السياق لاستخلاص التناقض من افتراض أن اللغة خالية من السياق.

بالطبع، إذا لم تكن لغتك قابلة للتقرير أو التعرف عليها، فيمكنك إثبات ذلك بطرق مختلفة أيضًا.