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

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

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

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

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

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

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка ? = а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*).

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

Статьи к прочтению:

Введение в теорию автоматов и вычислений. 1.16 Свойства регулярных языков

Похожие статьи: