2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Регулярные выражения.
Сообщение10.12.2012, 01:09 
Рассмотрим обычные регулярные выражения (которые эквивалентны КА), правда ли что ими нельзя задать язык строк в алфавите $\{a,b\},$ в каждой из которых подстрока $ab$ встречается столько же раз, сколько $ba$ ?

 
 
 
 Re: Регулярные выражения.
Сообщение10.12.2012, 01:14 
Аватара пользователя
Неправда.
А вот в алфавите $\{a,b,c\}$ задать нельзя.

 
 
 
 Re: Регулярные выражения.
Сообщение10.12.2012, 01:26 
А как это сделать в $\{a,b\}$? Подскажите идею?

 
 
 
 Re: Регулярные выражения.
Сообщение10.12.2012, 01:53 
Аватара пользователя
Подумайте, на сколько могут отличаться количество вхождений $ab$ и $ba$ и в каких случаях.

 
 
 
 Re: Регулярные выражения.
Сообщение10.12.2012, 12:22 
Точно)

Вот так правильно?
$a^+(b^+a^+)^*\, | \,b^+(a^+b^+)^*$

 
 
 
 Re: Регулярные выражения.
Сообщение10.12.2012, 13:49 
Аватара пользователя
Верно. Можно еще так: $(a(a|b)^*a)|(b(a|b)^*b)$

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group