Регулярность/нерегулярность языка (теория алгоритмов)

[Nikgamer]

Всем привет. Давно я тут не появлялся, ибо комп устроил флейм и стал героем, так что я две недели покупал новый. Собственно, у меня на первом курсе НГУ есть такой "замечательный" предмет под названием теория алгоритмов. По нему я и хотел спросить.

Задача.\
Имеется язык  L={aba^R, где a,b ∈∑* а^R - это слово, которое читается справа налево, т.е.это слово а, только прочитанное наоборот). Доказать, что язык L регулярный или нерегулярный.
Собственно, мои идеи.
по теореме "о накачке" никак не удается свести к противоречию (инфа 100%, все перепробовал, т.е. в качестве y брал и части от а и части от a^R). Соответственно подобрать противоречие и объявить его нерегулярным мы сходу не можем. Как разбить его на классы эквивалентности я тоже не очень представляю. И представить его в виде объединения, конкатенации и звездочки тоже сходу не выходит (т.е. записать как регулярное выражение). Есть еще вариант построить противоречие на том, что, скажем найти такие другие регулярные языки, что они в пересечении/объединении/дополнении будут давать этот язык, тогда он будет регулярный, но не знаю тоже как. Автомат для этого языка, очевидно, будет бесконечным, ибо даже палиндромный автомат бесконечен, а тут еще навороты.
Есть смельчаки?

[SmartStudent]

изучал этот предмет 2 года назад, так что если что-то не так напишу то строго не ругайте... ))

ну есть такая у меня идея
разве

наш язык не получится если ∑*\(a(a+b)*b объединить b(a+b)*a)?

Если нет, то приведи пример слова которое есть в моем языке и нету в твоем, или наоборот)

[Nikgamer]

а что это за подслово - a+b ?)

[SmartStudent]

(a+b)* = ∑*

ну то есть это означает буквально (или а или b)

например язык состоящий из 2х слов aab, abb
можно записать таким образом

а(а+b)b

[Nikgamer]

Я, наверное, забыл уточнить, что слово произвольной длины. Т.е. к примеру o(L)=n, а |xy|<=n
abbba разве подходит под твою ф-лу?

[SmartStudent]

не пойму про какую ты формулу говоришь, и не пойму что ты уточняешь:))
Но

abbba принадлежит (∑*\(a(a+b)*b объединить b(a+b)*a))

[SmartStudent]

короче я утверждаю что aba^R = a(a+b)*a Объединить с b(a+b)*b

Если я не прав то прошу пример.

[Nikgamer]

Проверил. Да, подходит. Дождусь встречи с семинаристом, посмотрю на его вердикт, ну вроде похожу на правду.

[SmartStudent]

будет интересно узнать вердикт семинариста))

[SmartStudent]

токо я наверно не точно написал
лучше так

xyx^R = a(a+b)*a Объединить с b(a+b)*b

где a,b - это буквы, а x,y-cлова

то есть x,y ∈∑*,  a,b ∈∑

[Nikgamer]

Итак, правильное решение. (для СмартСтудента)
этот язык регулярен, т.к. это просто весь ∑*
т.к. а∈∑* и b∈∑* то  b∈{aba^R} т.е. ∑*⊆{aba^R}⊆∑* соответственно.

[SmartStudent]

да точно)

[hyper]

Ребят, помогите доказать регулярность-нерегулярность языка :
L={aⁿ p aⁿ  | p∈{b,c}^* , n>=0 } в алфавите {a,b,c}

[Nikgamer]

По-моему, он не будет регулярным по лемме о накачке.
Пусть o(L)=n. Тогда, пусть w=xyz, где x,y,z из искомого алфавита, а w из L и оно произвольно.
Лемма утверждает, что:
1) |xy|<n
2)  y не равен e
3) для любого i>=0 из N xyⁱz снова лежит в языке.
Очевидное противоречие, т.к. из 1 и 2 условия следует, что x=a^k, где 0<k<n. Тогда xyⁱz=a^n-ka^kipaⁿ
Полагаем i=0 => a^n-kpaⁿ должен лежать в L. С учетом выбора k получаем противоречие.
Значит язык нерегулярный