как доказать, что язык не регулярен?

[hyper]

что язык $\L=\left\{a^n\phi a^n | \phi\ \epsilon \left\{b,c\right\}^*,n\geqslant 0\right\}$
не регулярен...

-- Чт апр 01, 2010 20:35:11 --

Язык не регулярен, когда не представим автоматом.
Вот как доказать, что нету автомата?

[Maslov]

У ДКА конечное число состояний.
Попробуйте, например, рассмотреть автомат с $n$ состояниями и цепочку $a^{n+1}ba^{n+1}$.

[hyper]

. . . $\uparrow $
$\circ \to \circ \gets\circ$
. . . $\downarrow$. .$\uparrow$
. . . $\circ\to\circ$
тут точки - это пробелы))


картинка такая? $n$ вершин


есть некая лемма о накачке, мб ей воспользоваться?

[Maslov]

Ну да.