كل لغة مريح $ L $ لديها مجموعة فرعية حائزة لانهائية $ S \ Subset L $ مثل $ l \ setminus s $ غير محدود

Question

بالنظر إلى لغة حاسمة لا حصر لها $ l $ ، ثم إذا كان $ s \ subset l $ مثل ذلك $ l \ setminus s $ هو محدود، ثم $ S $ يجب أن تكون حلول. هذا صحيح منذ إعطاء قرر $ l $ نحن تعذب قرارا $ S $ :

محاكاة قرر $ l $ على المدخلات، إذا كان يقبل، فانتقل إلى $ l \ setminus s $ وتحقق مما إذا كان هناك، إذا كان الأمر كذلك، فرفض. إذا لم يقبل. إذا كان عرض $ l $ يرفض - رفض.

نقطة أخرى هو إذا $ s \ subset l $ هو محدود ثم $ S $ يجب أيضا أن تكون أيضا مريح، هذا فوري أن كل لغة محدودة صالحة للحساس.

الآن لدينا الحالة الأخيرة حيث $ s $ غير محدود و $ l \ setminus s $ لا لانهائي. نحن نعلم أنه يجب أن يكون هناك بعض المجموعات الفرعية $ S $ المقابلة لهذه الحالة غير قابلة للتكرار. هذا منذ هناك $ \ alph $ مثل $ s $ ولكن $ \ aleph_0 $ المتكررين. تشير إلى $ d (l)={s \ subset l: | s |= | l \ setminus s |=infty \ wedge s \ text {هو مرحول} \} $ <} $ <} $ < / span>

هل صحيح أن اللغات اللانهائية الحائزة $ l $ لدينا $ d (l) \ neq \ phi $ ؟

إذا كان هذا صحيحا، فستكون نتيجة لذلك سيكون لدينا جميع اللغات اللانهائية اللانهائية $ l $ تسلسل اللغات المينة $ l_n $ مثل $ l_0= l $ و $ l_ {n + 1} \ subset l_n $ و $ | l_n \ setminus l_ {n + 1} |=INFTY $

سيكون لدينا أيضا الحد الأقصى $ l_ \ infty={e \ in l: \ forall n \ in \ mathbb {n} \ text {} e \ in L_N \} $ ويمكن dicuss إذا كان فارغا / محدود / لا نهائي ومقانوني أم لا.

يبدو أن هذا هو وسيلة لطيفة لدراسة اللغات الرائعة، والفضول لمعرفة ما إذا كان هذا الاتجاه مثير للاهتمام بالفعل وما إذا كانت هناك مقالات منشورة فيما يتعلق بهذه الأسئلة

شكرا لأي مساعدة

Answer 1

إذا كان $ L $ لديه أبجدية محددة، ثم $ l $ P>

بعد ذلك، من مثل هذا التعداد $ w_0، w_1، w_2، ... $ من كلمات $ l$ يمكنك أن تأخذ $ s={w_0، w_2، w_4، ... \} $ ، والتي ستكون أيضا حلولة أيضا.للتحقق مما إذا كانت كلمة $ W $ هي في $ s $ تحقق مما إذا كان ذلك في $ l $ .إذا كان يستخدمه بعد ذلك تعداد $ l $ للتحقق مما إذا كان موقفه هو حتى أم لا.