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

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

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

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

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