اگر w = xWz در اینصورت x را یک قطعه اولیه w و z را یک قطعه انتهایی w میگوییم ( x و W و z کاملاً دلخواه هستند بنابراین میتوانند رشته تهی نیز باشند.) فرض کنید: P(L) = x x قطعه اولیه رشتهای مانند w ∈ L است S(L) = x x قطعه انتهایی رشتهای مانند w ∈ L است P_2(L) = x ∃ y, y ≥ 2, xy ∈ L از سه عبارت زیر چه تعدادی درست است؟ الف) اگر L مستقل از متن باشد، آنگاه P(L) مستقل از متن است. ب) اگر L مستقل از متن باشد، آنگاه S(L) مستقل از متن است. ج) اگر L منظم باشد، آنگاه P_2(L) منظم است.

سوال ۸۸ کنکور ارشد علوم کامپیوتر ۱۴۰۲

نظریه زبان‌ها و ماشین‌هاسختزبان‌های مستقل از متن

اهمیت

۰/۵

اگر $w = xWz$ در این‌صورت $x$ را یک قطعه اولیه $w$ و $z$ را یک قطعه انتهایی $w$ می‌گوییم ( $x$ و $W$ و $z$ کاملاً دلخواه هستند بنابراین می‌توانند رشته تهی نیز باشند.) فرض کنید:

$P(L) = \{\, x \mid x \text{ قطعه اولیه رشته‌ای مانند } w \in L \text{ است} \,\}$

$S(L) = \{\, x \mid x \text{ قطعه انتهایی رشته‌ای مانند } w \in L \text{ است} \,\}$

$P_2(L) = \{\, x \mid \exists y,\; |y| \geq 2,\; xy \in L \,\}$

از سه عبارت زیر چه تعدادی درست است؟

الف) اگر $L$ مستقل از متن باشد، آنگاه $P(L)$ مستقل از متن است.

ب) اگر $L$ مستقل از متن باشد، آنگاه $S(L)$ مستقل از متن است.

ج) اگر $L$ منظم باشد، آنگاه $P_2(L)$ منظم است.

#context-free#closure-properties#prefix#suffix#regular-languages#right-quotient