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

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

اگر یک [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] کنه

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

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