Самый распространенный способ доказать, что язык НЕ является регулярным, - это использование Pumping Lemmas .
Использовать лемму немного сложно, поскольку в ней есть все те, которые существуют, и так далее. Чтобы доказать, что язык L не является регулярным, используя лемму прокачки, вы должны доказать, что
for any integer p,
there is a word w in L of length n, with n>=p, such that
for all possible ways to decompose w as xyz, with len(xy) <= p and y non empty
there exists an i such that x(y^i)z (repeating the y bit i times) is NOT in L
Whooo!
Я покажу, как выглядит доказательство для языка "с тем же числом as и bs". Это должно быть просто конвертировать в ваш случай:
for any given p, we can make a word of length n = 2*p
a^p b^p (p a's followed by p b's)
any way you decompose this into xyz w/ |xy| <=p, y will only contain a's.
Thus, pumping the the y part will make the word have more as than bs,
thus NOT belonging to L.
Если вам нужна интуиция о том, почему это работает, это следует из того, как вам нужно иметь возможность подсчитывать до произвольно больших чисел, чтобы проверить, принадлежит ли слово одному из этих языков. Однако регулярные языки описываются конечными автоматами, и никакие конечные автоматы не могут представлять бесконечное количество состояний, необходимых для представления всех чисел. (Статья в Википедии должна иметь формальное доказательство).
РЕДАКТИРОВАТЬ: Похоже, что вы не можете прямо использовать непосредственную лемму в этом конкретном случае: если вы всегда делаете y длинной в один символ, вы никогда не сможете заставить слово перестать быть принятым (аба, став abbbba, не делает разница и тд).
Просто используйте подход класса эквивалентности, предложенный Patrick87 - он, вероятно, окажется чище, чем любой из грязных хаков, которые вам нужно будет сделать, чтобы применить здесь лемму прокачки.