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

Иногда бывает необходимо доказать, является или нет некоторый язык регуляр­ным. Конечно, можно пойти путем поиска определения для цепочек заданного языка через один из рассмотренных выше способов (регулярные грамматики, ко­нечные автоматы и регулярные выражения). Если для этого языка хотя бы один из способов будет определен, следовательно, язык является регулярным (и на основании одного найденного способа определения языка можно найти осталь­ные). Но если не удается построить определение языка ни одним из этих спосо­бов, то остается неизвестным: то ли язык не является регулярным, то ли просто не удалось найти определение для него.

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

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

Формально эту лемму можно записать так: если дан язык L, то
 константа р>0, такая, что если αL и |α|р, то цепочку α можно записать в виде α=β, где 0<|β|р, и тогда α’ =βi, α’Li0.

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

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка α = аnbnи запи­шем ее в виде α=β. Если βа+или βb0+, то тогда для i=0 цепочка β0= не принадлежит языку L, что противоречит условиям леммы; если же βа+b+, тогда для i=2 цепочка β2=ββ не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.

Контекстно-свободные языки

3.1. Распознаватели КС-языков. Автоматы
с магазинной памятью

Определение МП-автомата

Контекстно-свободными (КС) называются языки, определяемые грамматиками типа G(VT,VN,P,S), в которых правила Р имеют вид: Аβ, где AVN и βV*, V=VTVN.

Распознавателями КС-языков служат автоматы с магазинной памятью (МП-автоматы).

В общем виде МП-автомат можно определить следующим образом:

R(Q,V,Z,,q0,z0,F),

где Q – множество состояний автомата; V – алфавит входных символов автома­та; Z – специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грам­матики), VZ;  – функция переходов автомата, которая отображает множество Q(V{})Z на конечное множество подмножеств P(QZ*); q0Q – начальное состояние автомата; z0Z – начальный символ магазина; FQ – множество ко­нечных состояний.

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные “магазинные” символы (обычно это терминальные и не­терминальные символы грамматики языка). Переход из одного состояния в дру­гое зависит не только от входного символа, но и от одного или нескольких верх­них символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (поло­жением указателя в цепочке) и содержимым стека.

МП-автомат условно можно представить в виде схемы на рис. 3.1.

Рис. 3.1. Общая условная схема автомата с магазинной памятью (МП-автомата)

Конфигурация МП-автомата описывается в виде тройки (q,α,)QV*Z*, кото­рая определяет текущее состояние автомата q, цепочку еще непрочитанных сим­волов α на входе автомата и содержимое магазина (стека) . Вместо α в конфи­гурации можно указать пару (β,n), где βV* – вся цепочка входных символов, а nN{0}, n0 – положение считывающего указателя в цепочке.

Тогда один такт работы автомата можно описать в виде (q,aα,z)  (q’,α,γ), если (q’,γ)(q,a,z), где q,q’Q, aV{}, αV*, zZ{}, γ,Z*. При выполнении такта (перехода) из стека удаляется верхний символ, соответствующий условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при кото­рых входной символ игнорируется (и тем самым он будет входным символом при следующем переходе). Эти переходы (такты) называются -переходами (-так­тами). Аналогично, автомат не обязательно должен извлекать символ из стека – когда z=, этого не происходит.

МП-автомат называется недетерминированным, если из одной и той же его конфигурации возможен более чем один переход.

Начальная конфигурация МП-автомата, очевидно, определяется как (q0,α,z0), αV*. Множество конечных конфигураций автомата – (q,,), qF, Z*.

МП-автомат допускает (принимает) цепочку символов, если, получив эту цепоч­ку на вход, он может перейти в одну из конечных конфигураций, когда при окончании цепочки автомат находится в одном из конечных состояний, а стек содержит некоторую определенную цепочку. Тогда входная цепочка принимает­ся (после окончания цепочки автомат может сделать произвольное количество -переходов). Иначе цепочка символов не принимается.

Язык, определяемый МП-автоматом, – это множество всех цепочек символов, которые допускает данный автомат. Язык, определяемый МП-автоматом R, обо­значается как L(R). Два МП-автомата называются эквивалентными, если они определяют один и тот же язык. Если два МП-автомата R1и R2определяют один и тот же язык, это записывается как L(R1) = L(R2).

МП-автомат допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из конечных состояний, а стек пуст – конфигурация (q,,), qF. Если язык задан МП-автоматом R, который допускает цепочки с опустошением стека, это обозначается так: L(R). Для любого МП-автомата всегда можно построить эквивалентный ему МП-ав­томат, допускающий цепочки заданного языка с опустошением стека. То есть МП-автомата R:
 МП-автомат R’, такой что L(R) = L(R’).

Кроме обычного МП-автомата существует также понятие расширенного МП-автомата.

Расширенный МП-автомат может заменять цепочку символов конечной длины в верхней части стека на другую цепочку символов конечной длины. В отличие от обычного МП-автомата, который на каждом такте работы может изымать из сте­ка только один символ, расширенный МП-автомат может изымать за один такт сразу некоторую цепочку символов, находящуюся на вершине стека. Функция переходов  для расширенного МП-автомата отображает множество Q(V{})Z* на конечное множество подмножеств P(QZ*).

Доказано, что для любого расширенного МП-автомата всегда можно построить эквивалентный ему обычный МП-автомат (обратное утверждение очевидно, так как любой обычный МП-автомат является и расширенным МП-автоматом). Та­ким образом, классы МП-автоматов и расширенных МП-автоматов эквивалент­ны и задают один и тот же тип языков.