حدد ما إذا كانت اللغة تحتوي على كلمة بحجم معين

Question

لنفترض أن $ L $ هي بعض اللغات عبر الأبجدية $ \ sigma $ . طلب مني إظهار أن اللغات التالية صالحة للحساس:

$$ L '={w \ in \ sigma ^ * | \ text {هناك كلمة} W '\ in l \ text {مثل ذلك} | W' | \ leq | W | \} $$

IE، $ w \ in l '$ إذا كان $ l $ لديه بعض الكلمة مع طول أصغر من $ | W | $ .

الطريقة التي كنت أفكر فيها في إظهار أن $ l \ cap \ sigma ^ {| w |} $ هو محدود، و $ (l \ cap \ sigma) \ كأس (l \ cap \ sigma ^ 2) \ cup \ ldots \ كأس (l \ cap \ sigma ^ {| w |}) $ هو محدود أيضا، وبالتالي حتى. لكن الشيء الرئيسي الذي يكافح فيه هو كيف يمكن لأي خوارزمية $ l $ تعرف إذا كانت بعض $ u \ in l $ ؟ هذا غير قابل للترشف، لذلك من غير الواضح بالنسبة لي كيف يمكن لأي خوارزمية $ l $ يمكن التحقق منها بالفعل بعض الكلمة في $ L $

Answer 1

هناك حالتان:

1. $ l $ فارغ. في هذه الحالة، $ l '=emptyset $
2. $ l $ غير فارغ. دع $ m $ يكون الحد الأدنى لطول الكلمة في $ l $ . ثم $ l $ يتكون من جميع كلمات الطول على الأقل $ M $ ، ويتم مرة أخرى بشكل تافه (في وقت ثابت!).

كما ترون، لن تحتاج أبدا إلى خوارزمية ل $ l $ .

---

وبالمثل، فإن اللغة التالية منتشرة دائما:

$$ l ''={w \ in \ sigma ^ * \ mile \ text {هناك كلمة $ w '\ in l $ @ هذه $ | | \ GEQ | W | $} \}. $$

هناك الآن ثلاث حالات:

1. $ l $ فارغ. في هذه الحالة، $ l ''=emptyset $
2. $ l $ غير محدود. في هذه الحالة، $ l ''=sigma ^ * $ مرة أخرى triviall الميميل.
3. $ l $ هو محدود. دع $ M $ يكون الحد الأقصى لطول الكلمة في $ l $ . ثم $ L '' $ يتكون من جميع كلمات الطول على معظم $ M $ ، ويعتبر تافهة مرة أخرى حلول (في وقت ثابت).

---

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