سلام
من دلیل اینکه برای یه سری گفته احتیاج ب حافظه کمکی داره ویه سری روگفته نداره متوجه نمیشم ممنونم کسی توضیح بده
سلام
دوست گرامی زبان های منظم نیاز به حافظه کمکی ندارند ولی زبان های دیگر مثل مستقل از متن برای تشخیص نیاز به حافظه کمکی مثل پشته دارند.
در زبان های مستقل از متن معمولا(نه همیشه) یک نوع وابستگی بین عناصر تشکیل دهنده ان وجود دارد مثلادر [tex]\{ww^Rv\: :\: v\: ,\: w\: \in\{a,b\}^+\}[/tex] یک وابستگی وجود دارد یعنی ماباید تا قیل از رسیدن به [tex]W^R[/tex] باید بدانیم چه نماد های پیمایش شده تا از این به بعد معکوس ان را بررسی کنیم پس باید اطلاعاتی درباره W را در یک حافظه کمکی (مثلا پشته یا نوار) ذخیره کنیم تا موقع رسیدن به معکوس W بتوانیم درستی ان را بررسی کنیم. باید توجه کرد که نباید فقط به ظاهر زبان توجه کرد مثلا در [tex]\{uww^Rv\: :\: u,v,w\in\{a,b\}^{\ast}\}[/tex] باز وابستگی داریم ولی این زبان نیاز به حافظه کمکی ندارد چون برخلاف ظاهرش زبانی منظم است.
دلیل منظم بودن: با توجه به اینکه u , v , w عضو [tex]\{a,b\}^{\ast}[/tex] هستند پس می توانند رشته تهی را هم بگیرند. حالا این مقدار دهی را در نظر بگیرید.
[tex]u=\sum^+\: \: ,\: \: \: w=\lambda\: \: \: ,\: \: v=\lambda[/tex] اگر در زبان قرار دهیم زبان [tex]\sum^+[/tex] حاصل می شود که زبانی منظم است در واقع در این حالت مقدار دهی خاص رشته های تولیدی این زبان همان رشته های تولیدی [tex]\sum^+[/tex] است حال مقدار دهی های دیگر هم رشته های تولید می کند که باید کل رشته ها با هم اجتماع شود تا رشته های زبان ما بدست اید ولی اجتماع رشته های سایر مقدار دهی با [tex]\sum^+[/tex] باز هم همان [tex]\sum^+[/tex] می شود.توجه شود که زبان ما رشته تهی ندارد چون برای رسیدن به این منظور بایدu,v,w هرسه مقدار تهی را بگیرند ولی با توجه به شرط [tex]|u|\ne|v|[/tex] امکان پذیر نیست.در واقع اگر u,v هر دو رشته تهی بگیرند طولشان برابر می شود که نقض شرط است