۰
subtitle
ارسال: #۱
سوال از زبان مستقل از متن
اگر [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]
[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]
۰
ارسال: #۲
RE: سوال از زبان مستقل از متن
در مورد اولی یه راهنمایی میکنم اگر حل نشد حل کاملش رو ارسال میکنم.
زبان اولی به روایتی دیگر یعنی اگر در کلمه مورد نظر یک عدد ۱ در ۱/۳ میانی وجود داشت این کلمه در زبان وجود دارد.
زبان اولی به روایتی دیگر یعنی اگر در کلمه مورد نظر یک عدد ۱ در ۱/۳ میانی وجود داشت این کلمه در زبان وجود دارد.
۰
۰
ارسال: #۴
RE: سوال از زبان مستقل از متن
برای دومی روی این کلمه از پامپینگ لم استفاده کنی فکر کنم حل بشه
$۰^n10^{n-2}10^n$
$۰^n10^{n-2}10^n$
۰
ارسال: #۵
RE: سوال از زبان مستقل از متن
اثبات مستقل از متن بودن زبان اولی:
[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 به گونه ای این فضا (ابتدا یا انتهای رشته میانی ) پر می شود که نهایتا پس از اتمام اشتقاق تکه ی میانی حداقل یک ۱ داشته باشد.
دقت داشته باشید که زبان ما رشته های دو کاراکتری یا چهار کاراکتری ندارد.
[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 به گونه ای این فضا (ابتدا یا انتهای رشته میانی ) پر می شود که نهایتا پس از اتمام اشتقاق تکه ی میانی حداقل یک ۱ داشته باشد.
دقت داشته باشید که زبان ما رشته های دو کاراکتری یا چهار کاراکتری ندارد.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close