Лемма о разрастании для регулярных языков

Лемма о разрастании для регулярных языков

Существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разрастании языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является [6, т. 1].

Лемма о разрастании для регулярных языков формулируется следующим образом: если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким способом новые цепочки будут принадлежать тому же регулярному языку. (Если найденную подцепочку повторять несколько раз, то исходная цепочка как бы «разрастается» — отсюда и название «лемма о разрастании языков»).

Формально эту лемму можно записать так: если дан язык L, то $ константа р > 0, такая, что если aÎL и |a| ³ р, то цепочку a можно записать в виде a = dbe, где 0 < |b| < р, и тогда a' = dbⁱe, a'ÎL "i ³ 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {аⁿЬⁿ | n > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка a = аⁿЬⁿ и запишем ее в виде a = dbe. Если bÎa⁺ или bÎb⁺ то тогда для i = 0 цепочка db⁰e = de не принадлежит языку L, что противоречит условиям леммы; если же bÎa⁺b⁺, тогда для i = 2 цепочка db²e = dbbe не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.