تالار گفتمان مانشت

سلام
خسته نباشید
میخواستم این ۲تا سوال رو با لم تزریق (همون ۴ مرحله) حل کنید!
حیلی ممنون!
a^pq به طوریکه p و q فرد هستند
و
a^m به طوریکه m را نمی توان به صورت حاصلضرب دو عدد نوشت که نسبت به هم اولند!

سلام. اولی که منظمه. میشه نوشت [tex]a(aa)^*[/tex].

برای دومی مکمل زبان رو درنظر میگیریم. مکمل زبان رو [tex]L'=\{a^{p^q}|p:prime\}[/tex] تعریف میکنیم. روی رشته [tex]w=xyz=a^{2^M}[/tex] میشه از لم تزریق استفاده کرد. فرض میکنیم [tex]|y|=k[/tex]. رشته [tex]w'=xy^{2^{M 1} 1}z=a^{2^M(2k 1)}[/tex] به دلیل اینکه [tex]2^M[/tex] و [tex]2k 1[/tex] نسبت بهم اولن جزء مکمل زبان نیست. پس زبان و مکملش منظم نیستن.