زبان زیر مستقل از متنه. چرا؟
[tex]L=uvwv^{R}: u,v,w \in a,b^{ } , \left | u \right |=\left | w \right |=2[/tex]
اینجا هم باید معکوس u رو چک کنه و هم این که طول u و w برابر باشه.
اگه بخواهیم با پشته پیاده سازیش کنیم ابتدای رشته را برای چک اینکه طولش با w یکی باشه میذاره توی پشته، بعد vها را هم برای چک معکوس بعدی باید بذاره توی پشته ولی بعدش که w هست!!! چکار میکنه؟ چطوری طولش با طول u چک میشه؟؟؟؟ چون الان روی پشته v هست!!!
یا اینکه خودش می فهمه ۲ تا یعنی چی و از اول رشته ۲ تا میره جلو؟
یکم سخت شد:دی
ولی فکر کنم چون ۲=|u| است و یا aa است یا bb یا ab یا ba و فقط کافیه که u ,w اندازشون ۲ باشه.
گرامرشو میشه اینجوری نوشت:
[tex]S\rightarrow AB[/tex]
[tex]A\rightarrow ab |ba|aa|bb[/tex]
[tex]B\rightarrow wAw^{R}[/tex]
منظورم از این [tex]B\rightarrow wAw^{R}[/tex] گرامر این زبان هست یعنی الان فقط نماد نوشتم .
فکر کنم چیزی که گفتید میتونه درست باشه
یعنی چون تعداد حالات محدوده میتونیم همه حالات رو به هر حال بررسی کنیم حتی اگه طولشون برابر با ۱۰۰ بود.
ولی اگه فقط گفته بود طول u و w با هم برابره و نگفته بود برابر چند اونوقت مستقل از متن نبود نه؟
نمی دونم شایدم اشتباه می گم!! اون موقع پس چطوری توی پشته میذاره!!
نه دیگه اونوقت مستقل از متن نبود.
من فکر میکنم برای این حالت بتونیم بگیم که درسته که الان v روی پشته است ما هم کاری نداریم فقط به طور غیرقطعی دو تا از حروف ورودی رو ازش میگذریم یعنی میگیم این دو حرف نقش w رو داشته.
(۱۱ بهمن ۱۳۸۹ ۰۹:۱۸ ق.ظ)afagh1389 نوشته شده توسط: یکم سخت شد:دی
ولی فکر کنم چون ۲=|u| است و یا aa است یا bb یا ab یا ba و فقط کافیه که u ,w اندازشون ۲ باشه.
گرامرشو میشه اینجوری نوشت
[tex]S\rightarrow AB[/tex]
A----> ab |ba|aa|bb
[tex]B\rightarrow WW^{R}|A[/tex]
منظورم از این [tex]B\rightarrow WW^{R}[/tex] گرامر این زبان هست یعنی الان فقط نماد نوشتم .
من متوجه نشدم
رشته و معکوسش که اصلا کنار هم نیستند توی زبان که
چرا نوشتین ww^R؟ بعد اون A چیه؟
گفتم که این نماده!
منظورم از A این بود که شما وقتی WWR رو پیاده سازی کردین وسطش A رو قرار بدین.
آهان آره همین طوری ۲ تا برمیداریم
بعد از چک کردن معکوس اگر توی پشته ۲ تا حرف فقط مونده بود پذیرفته میشه
مثل وقتی که
[tex]wcw^{R}[/tex]
رو پیاده سازی میکردین حالا
[tex]vAv^{R}[/tex]
رو پیاده سازی کنید.