تالار گفتمان مانشت
دو گزاره درموردطول پشته ی pdaها - نسخه‌ی قابل چاپ

دو گزاره درموردطول پشته ی pdaها - pooyaa - 06 بهمن ۱۳۹۳ ۰۶:۴۹ ب.ظ

سلام

درستی گزاره های زیر رو میخواستم:
۱-اگر یک pda برای هرورودی کمتر از n حرف در پشته اش push کند آنگاه زبانی که میپذیرد منظم است.
۲-اگر یک pda برای هرورودی بطول n کمتر از n حرف در پشته اش push کند آنگاه زبانی که میپذیرد منظم است.

RE: دو گزاره درمورد pdaها - Jooybari - 07 بهمن ۱۳۹۳ ۰۱:۱۰ ق.ظ

سلام.
در مورد سوال ۱ اگه منظورتون اینه که از یه حافظه محدود و مستقل از طول رشته استفاده کنیم زبان منظم میشه.
سوال ۲ منظم نیست.

RE: دو گزاره درمورد pdaها - fatemeh69 - 07 بهمن ۱۳۹۳ ۰۱:۴۲ ق.ظ

(۰۷ بهمن ۱۳۹۳ ۰۱:۱۰ ق.ظ)Jooybari نوشته شده توسط:  سلام.
در مورد سوال ۱ اگه منظورتون اینه که از یه حافظه محدود و مستقل از طول رشته استفاده کنیم زبان منظم میشه.
سوال ۲ منظم نیست.

چطور می شه اثیات کرد که سوال ۲ منظم نیست؟

RE: دو گزاره درمورد pdaها - MiladCr7 - 07 بهمن ۱۳۹۳ ۰۲:۰۳ ق.ظ

سلام ببخشید البته خود اساتید هستند ولی چون قبلا این سوالو دیدم گفتم مثالشم خدمتتون بگم

توی علوم کامپیوتر ۹۰ یه سوال اومده درستی یا نادرستی ۴ تا عبارت رو خواسته که یکی از گزینه ها این هستش:

اگر یک [tex]PDA[/tex] برای هر ورودی به طول [tex]n[/tex]، کمتر از [tex]n[/tex] حرف در پشته اش [tex]Push[/tex] کند، ان گاه زبانی که میپذیرد منظم است.
میگیم اشتباهه. چون زبانی مثل [tex]L=\{a^pb^pcca^mb^k|p,m,k>=0\}[/tex] که نامنظم و مستقل از متن هستش برای هر ورودی به طول [tex]n[/tex]، نیازی نداره که [tex]n[/tex] حرف رو تو پشته [tex]Push[/tex] کنه

RE: دو گزاره درمورد pdaها - Jooybari - 07 بهمن ۱۳۹۳ ۰۴:۱۰ ق.ظ

سوال گفته کمتر از n حرف که طول رشتست رو پوش کنه. اگه این مقدار وابسته به n نباشه منظمه. ولی اگه به n وابسته باشه مثلاً n/2 یا n/5 یا هر مقدار دیگه مستقل از متن میشه.