سلام
چرا میگن عبارت منظم نیست؟
{a^n , n>0 and n is prime}
اگر خیلی ساده به سوال پاسخ دهم، اینطور کی گویم که چون نمی توان همه اعداد اول را با تعداد محدودی از حالت ها ایجاد نمود پس این زبان منظم نیست.
ولی اگر قصد اثبات با روش های آکادمیک را داشته باشیم باید گفت که اثبات غیر منظم بودن زبان با استفاده از لم پامپینگ امکان پذیر است. روند اثبات در زیر آمده است :
- حریف ادعا می کند، به ازای رشته های به طول بزرگتر از m در این زبان، رشته های این زبان تنها با تکرار قسمتی از آن در حال بزرگ شدن است (این خاصیت زبان های منظم است و اگر زبانی این خاصیت را نداشته باشد منظم نیست ولی اگر داشته باشد لزوما منظم نیست).
- ما برای اینکه حریف را ضایع کنیم، رشته ای به طول 'm انتخاب می کنیم که [tex]m'>m[/tex] است و اول می باشد. از حریف می خواهیم که تمام تلاشش را انجام دهد تا به ما نشان دهد در کجای رشته های زبان، این تکرار رخ می دهد.
- حریف بهترین تفکیک را برای اینکه حرفش را به کرسی بنشاند و ثابت کند که زبان منظم است را به صورت زیر بیان می کند :
[tex]x\: =\: a^{k1}[/tex]
[tex]y\: =\: a^{k2}[/tex]
[tex]z=a^{m'-k1-k2}[/tex]
[tex]k1 k2\: \le m[/tex]
[tex]k2\: \ge1[/tex]
با توجه به ادعای حریف، رشته های به طول بزرگتر از m در این زبان، دارای ساختار زیر هستند :
[tex]W_i=a^{k1}(a^{k2})^ia^{m'-k1-k2}=a^{m' (i-1)k2}[/tex]
حال ما برای ضایع کردن او، i را طوری انتخاب می کنیم که رشته حاصل از الگوری فوق، در زبان نگنجد :
[tex]i=m' 1[/tex]
با انتخاب این مقدار i، رشته حاصل از الگوی فوق به صورت زیر خواهد شد :
[tex]a^{m'(1 k2)}[/tex]
از آنجا که 'm اول است. وقتی در عددی ضرب شود، حاصل اول نخواهد بود. یعنی طول رشته حاصل اول نیست. بنابراین بر خلاف ادعای حریف، رشته های بزرگتر از m، از چنین الگویی پیروی نمی کنند. بنابراین این زبان اول نیست.