تالار گفتمان مانشت
رسم pda برای L=a^nb^m با شرط n<=m<=2m - نسخه‌ی قابل چاپ
رسم pda برای L=a^nb^m با شرط n<=m<=2m - لهمشد - ۱۶ خرداد ۱۳۹۰ ۰۸:۳۶ ب.ظ

با سلام:
ممکنه بگید pda این زبان رو چطور رسم میکنید ؟
کد:
L=a^nb^m
به شرطی که
کد:
n<=m<=2m
RE: رسم pda - ف.ش - ۱۶ خرداد ۱۳۹۰ ۰۹:۲۶ ب.ظ

فکر کنم n<=m<=2n بوده.

این یک میان گرامر بین گرامری که برای [tex]a^{n}b^{n}[/tex] و گرامر برای [tex]a^{n}b^{2n}[/tex]

هست.

[tex]S\rightarrow aSb|aSbb|ab|abb[/tex]

شما هر رشته ای که تولید میکنید تعداد b‌ها از تعداد a‌ها کمتر نمیشه و تعداد b‌ها هم از دوبرابر تعداد a‌ها بیشتر نمیشه.