Да се докаже,че е регулярен език

[simonan]

Здравейте,

Имам затруднение с тази задача :
Трябва да се докаже,че езика е регулярен над азбуката ={a,b,c,d}
Езика,съдържа думи от вида w=[tex]a_{1}a_{2}a_{2n-1}a_{2n}[/tex] ,за някое [tex]n\in[/tex]N и [tex]a_{i}[/tex] принадлежи на азбуката за i=1....2n ,за които [tex]a_{2j-1}=a_{2j}[/tex] за j=1...n и освен това w съдържа не повече от три срещанияна буквата 'd' .

Опитах се да го докажа по следния начин: чрез регулярен израз
Израза е (aa)*(bb)*(cc)*(ee)*....(zz)*ddd(aa)*(bb)*(cc)*(ee)*....(zz)*
Искам да попитам дали е вярно и дали този израз е същият като : (aabbccee....zz)*ddd(aabbccee....zz)*

Благодаря предварително!

[simonan]

Объркала съм

регулярни израз да е (aa)*(bb)*(cc)*ddd(aa)*(bb)*(cc)*

[drago]

Няма как това да е регулярния израз. Три последователни d-та не могат да стоят едно след друго, защото по условие трябва да вървят по двойки и има ли три d-та ще трябва да има и четвърто, което е забранено.
Предлагам да пробваш стъпка по стъпка. Първо построй регулярен език, който генерира буквите по двойки без забраната да има повече от три d-та.
Примерно граматиката може да е следната:
[tex]S\to Saa[/tex]
[tex]S\to Sbb[/tex]
[tex]S\to Scc[/tex]
[tex]S\to Sdd[/tex]
[tex]S\to \emptyset[/tex]

След това да видим как да модифицираме горната граматика, така че да изключим появата на повече от една двойка d-та.
Например [tex]S\to Sdd[/tex] го махаме и на негово място слагаме [tex]S\to S'dd[/tex]. След което добавяме:
[tex]S' \to S'aa[/tex]
[tex]S' \to S'bb[/tex]
[tex]S' \to S'cc[/tex]
[tex]S'\to \emptyset[/tex]
Т.е. влезем ли в [tex]S'[/tex] няма да генерираме повече d-та.
Това е!

[simonan]

Благодаря!