دو گزاره درموردطول پشته ی 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 یا هر مقدار دیگه مستقل از متن میشه. |