اگر [tex]\sum\{0,1\}[/tex] و [tex]C1=\{xyz||x,z\in\sum\ast\: and\: y\in\sum\ast1\sum\ast\: where\: |x|=|z|\ge|y|\}[/tex]
[tex]C2=\{xyz||x,z\in\sum\ast\: and\: y\in\sum\ast1\sum\ast1\sum\ast\: where\: |x|=|z|\ge|y|\}[/tex]
ثابت کنید c1 مستقل از متن است
c2 مستقل از متن نیست[/align]
در مورد اولی یه راهنمایی میکنم اگر حل نشد حل کاملش رو ارسال میکنم.
زبان اولی به روایتی دیگر یعنی اگر در کلمه مورد نظر یک عدد ۱ در ۱/۳ میانی وجود داشت این کلمه در زبان وجود دارد.
میشه حل کاملشو بزارین
برای دومی روی این کلمه از پامپینگ لم استفاده کنی فکر کنم حل بشه
$۰^n10^{n-2}10^n$
اثبات مستقل از متن بودن زبان اولی:
[tex]S\rightarrow P1P|A|B[/tex]
[tex]P\rightarrow0|1[/tex]
[tex]A\rightarrow PPAP|C|E[/tex]
[tex]B\rightarrow PBPP|D|E[/tex]
[tex]C\rightarrow10|100|1000|1100|0100[/tex]
[tex]D\rightarrow01|001|0001|0011|0010[/tex]
[tex]E\rightarrow11|111|1111|101|010|1001|1011|1101|1010|0101|0110|0111|1110|110|011[/tex]
قوانین A و B رشته هایی سه تکه تولید می کنند که هر تکه می تواند هر تعداد ۰و۱ داشته باشد در نهایت متغیر جایی از رشته می ماند که یا شروع تکه ی میانی است یا پایان تکه ی میانی است.
حالا با رشته های D,E,C به گونه ای این فضا (ابتدا یا انتهای رشته میانی ) پر می شود که نهایتا پس از اتمام اشتقاق تکه ی میانی حداقل یک ۱ داشته باشد.
دقت داشته باشید که زبان ما رشته های دو کاراکتری یا چهار کاراکتری ندارد.