32
правки
Изменения
Нет описания правки
:где «<tex>.</tex>» – любой одиночный символ.
* Запишем регулярное выражение для языка <tex>L=b^kab^kab^ka</tex>. Данный язык не является ни регулярным, ни контекстно-свободным (по [[Лемма о разрастании для КС-грамматик|лемме о разрастании]]), но также легко представим с помощью обратных ссылок:
:<tex>L=(b\{b\}^*a)\backslash 1\backslash 1</tex>.
