Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика»

Методическая разработка предназначена для самостоятельной работы студентов специальности «Прикладная информатика» над материалом темы «Концепции конечного автомата и регулярного языка. Операции над регулярными языками», входящей в состав учебного курса «Теория алгоритмов и математическая логика». Вводятся понятие формального языка и действия над формальными языками, включая основные теоретико-множественные операции. Излагается концепция конечного автомата (в детерминированном и недетерминированном вариантах); регулярные языки представляют собой класс языков, распознаваемых конечными автоматами. Показывается, что операции, объединения, пересечения, дополнения, конкатенации и итерации не выводят из класса регулярных языков. Приводятся соответствующие алгоритмы синтеза конечных автоматов.

Составители:

преподаватели кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ доцент, д.т.н. Коган Д.И. и ассистент Бабкина Т.С.

Если  и  – два произвольных слова в алфавите А, то  – результат приписывания справа слова  к слову . Для любых слов  и  считаем, что ==, =.

Язык L в алфавите А называем универсальным, если L=А*. Язык L называем пустым, если множество L пусто (L=).

Пусть L₁ и L₂ – языки в алфавите А. Через L₁L₂ и L₁L₂ будем

обозначать объединение и пересечение этих языков соответственно. Слово  принадлежит объединению двух языков, если оно принадлежит по меньшей мере одному из них; слово  принадлежит пересечению двух языков, если оно принадлежит как одному, так и другому языку. Пусть L – язык в алфавите А; через L^с будем обозначать дополнение этого языка. Язык L^с образуют слова алфавита А, не входящие в состав языка L: L^с=А*\L. Операции объединения, пересечения и дополнения – основные теоретико-множественные операции.

Пусть L₁ и L₂ – языки в алфавите А. Через L₁\L₂ будем обозначать разность языков L₁ и L₂ . Слово  из А* считается принадлежащим L₁\L₂ тогда и только тогда, когда оно принадлежит языку L₁, но не принадлежит языку L₂. Очевидно, что операция разности представима через основные теоретико-множественные операции: L₁\L₂=L₁(L₂)^с.

Дополнительно введем несколько специальных операций над языками. Пусть L₁ и L₂ – языки в алфавите А. Через L₁L₂ обозначим язык, определяемый следующим образом: слово  принадлежит языку L₁L₂ тогда и только тогда, когда это слово можно разбить на две последовательные части (т.е. представить в виде =₁₂) так, что первая часть является словом языка L₁, а вторая часть – словом языка L₂. Операция  называется конкатенацией (сцепкой) языков. Знак  нередко будет опускаться, тогда конкатенация языков L₁ и L₂ записывается L₁L₂. Язык L₁L₂ получается приписыванием к словам языка L₁ слов языка L₂ в качестве окончаний. Отметим, что если к произвольному слову  приписать в качестве окончания пустое слово, то результатом будет слово . Если языки L₁ и L₂ конечны, причем в составе первого языка m слов, а в составе второго n слов, то язык L₁L₂ состоит максимум из mn слов. Если один из языков L₁, L₂ пуст, то L₁L₂ – также пустой язык.

Введем операцию возведения языка в степень. Полагаем:

L⁰={};

L¹=L;

L²=LL;

Lⁿ⁺¹=LⁿL, n=2, 3, ...;

таким образом, понятие степени Lⁱ языка L определено для любого i=0, 1, 2, 3, ... .

Далее через L^* обозначим объединение всех степеней языка L:

L*=Lⁱ.

Введенную операцию именуем итерацией. Отметим, что пустое слово принадлежит итерации любого языка. Непустое слово  принадлежит итерации языка L тогда и только тогда, когда это слово можно разбить на некоторое количество последовательных частей (подслов) так, что каждая часть принадлежит языку L. Если язык L состоит из всех однобуквенных слов алфавита А, то итерацией этого языка является универсальный язык А*. Отметим, что для любого языка L имеет место (L*)*=L*.

На множестве языков иногда рассматривают и следующую одноместную операцию ( )⁺:

(L)⁺=Lⁱ.

Языки L* и L⁺ отличаются один от другого разве что пустым словом. Слово  всегда принадлежит языку L*. Языку L⁺ оно принадлежит тогда и только тогда, когда принадлежит языку L.


2. Концепции конечного автомата и регулярного языка.
В кибернетике автоматами называют технически или программно реализованные модули, предназначенные для переработки поступающей информации. Конечный автомат – это модуль, имеющий конечное число возможных состояний и функционирующий в дискретном времени. В данном пособии конечные автоматы изучаются как абстрактные алгоритмические устройства, предназначенные для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова  во входном алфавите А автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние; состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над словом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.

Формально конечный автомат К определяем как совокупность

где Q={q₀, q₁, q₂, ..., q_m} – множество состояний автомата; А={а₁, а₂, ..., а_n} – входной алфавит; q₀ – специально выделенное состояние автомата, именуемое начальным состоянием; g – функция переходов конечного автомата, представляющая собой отображение типа QxАQ (если g(q_i,а_j)=q_k, то автомат из состояния q_i под воздействием буквы а_j должен перейти в состояние q_k); F – специально выделенное подмножество состояний автомата, которые мы условно будем именовать «хорошими», F Q.

Пусть – входное слово, l()=р. Через q_(t) обозначим состояние, в котором оказывается автомат К через t тактов работы над этим словом (здесь t=0, 1, 2, ..., р):

q

_(0)=q₀;

. . .

Будем говорить, что слово  принимается автоматом К, если q_(р)F. Введем в рассмотрение язык L(К): слово  принадлежит языку L(К), если данное слово принимается автоматом К. Язык L(К) именуем языком, распознаваемым данным конечным автоматом. Язык L назовем регулярным, если для него можно построить распознающий конечный автомат.

Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представляет собой ориентированный граф, вершины которого одноименны состояниям автомата; дуга из вершины q_i, в вершину q_k с надписанной над ней буквой а_j проводится тогда и только тогда, когда g(q_i,а_j)=q_k. В случае, когда переход из q_i в q_k осуществляется под воздействием любой из букв некоторого подмножества S, SА, все буквы этого подмножества подписываются над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись «xS» или просто «S»). Если произвольное состояние q_i входит в F, то данный факт на диаграмме отмечается жирным кружком, выделяющим вершину q_i.

Очевидно, что любой конечный автомат полностью определяется своей диаграммой переходов. Далее под задачей построения конечного автомата, обладающего теми или иными свойствами, будет пониматься задача построения

диаграммы его переходов.

На рис. 2.1 показана диаграмма автомата K₁, работающего над словами алфавита A={a,b,c}. Автомат имеет два состояния, q₀ и q₁, причем «хорошим» является только состояние q₁. Начав работу в состоянии q₀, автомат под воздействием букв a, b из этого состояния не выходит; под воздействием буквы с реализуется переход в состояние q₁; любая далее поступающая буква оставляет автомат в том же состоянии. Таким образом, автомат K₁ распознает язык L₁, состоящий из слов, имеющих в своем составе букву с. Данный язык является регулярным.

Приведем еще несколько примеров регулярных языков в том же алфавите: L₂ - множество слов, в которых буква а встречается четное число раз; L₃ - множество слов, начинающихся и заканчивающихся одинаковой буквой; L₄ - множество слов, содержащих подслово =abbc; L₅ - множество слов, при чтении которых слева направо разность между числом встреченных букв a и b никогда не превосходит 2. Диаграммы конечных автоматов K₂ - K₅, распознающих языки L₂ – L₅ соответственно, представлены на рисунках 2.2 – 2.5. Информацию об обработанной части входного слова автомат “помнит” своим состоянием. Так, например, автомат K₅, обработав некоторую часть входного слова, оказывается в состоянии q_x, если в прочитанной им части входного слова число встреченных букв а превышает число встреченных букв b на x; здесь x{-2, -1, 0, 1, 2}; автомат оказывается в состоянии q_плох, если в некоторый момент работы автомата абсолютная величина разности между числом обработанных букв а и числом обработанных букв b превысила 2.

Можно считать, что каждый автомат имеет не более одного положительно поглощающего и не более одного отрицательно поглощающего состояния (если положительно или отрицательно поглощающих состояний несколько, то они легко могут быть заменены одним). Обычно в диаграмме переходов отрицательно поглощающее состояние не изображается; если из некоторого состояния по некоторой букве переход не указан, то предполагается, что он ведет в отрицательно поглощающее состояние. Представленный на рисунке 2.6 конечный автомат распознает в алфавите А язык, состоящий из слов, в которые буква с входит ровно один раз. Этот автомат имеет 3 состояния, отрицательно поглощающее состояние q_плох (в него автомат переходит из состояния q₁ по букве с) в диаграмме не указано.

Введем алфавит B={0, 1, 2, …, 9}, каждое слово в этом алфавите трактуем как целое неотрицательное число. Пусть L^(p) обозначает множество слов – записей в десятичной системе счисления всех целых неотрицательных чисел, кратных натуральной константе p; будем считать, что языку L^(p) дополнительно принадлежит также пустое слово . Покажем, что L^(p) – регулярный язык. Распознающий L^(p) конечный автомат К^(p) можно построить следующим образом. Состояниями автомата считаем q₀, q₁, q₂, q_p–1; из произвольного состояния q_i по цифре х, х{0, 1, 2, ... ,9}, автомат переходит в состояние q_j, если остаток от деления числа iх (т.е. числа, получаемого приписыванием к числу i цифры х справа) на p равен j. Благодаря указанной структуре переходов автомат, обработавший, начиная от начального состояния q₀, записанное в десятичной системе счисления целое неотрицательное число , оказывается в состоянии q_y тогда и только тогда, когда остаток от деления  на p равен у. Единственным «хорошим» состоянием автомата К^(p) следует считать q₀. На рис. 2.7 и 2.8 представлены диаграммы конечных автоматов, распознающих числа, делящиеся на 2 и на 3 соответственно.

Отметим, что в ряде случаев, исходя из иных принципов, можно построить распознающие делимость на p автоматы c меньшим числом состояний. На рис. 2.9 представлен имеющий два состояния конечный автомат, распознающий числа, кратные пяти (используется тот факт, что кратное пяти число имеет своей последней цифрой 0 или 5).

По конечному автомату К^(p) легко строится автомат К^(p)[], распознающий язык L^(p)\{}. Для получения диаграммы переходов автомата К^(p)[] в имеющейся диаграмме переходов автомата К^(p) делаются следующие изменения: начальное состояние q₀ автомата К^(p) переименовываем в q₀; вводим новое начальное состояние q₀; по произвольной цифре х из q₀ автомат К^(p)[] реализует переход в то же состояние, что и автомат К^(p) из своего начального состояния (при этом вместо перехода в q₀ всегда реализуется переход в q₀); единственным «хорошим» состоянием автомата К^(p)[] следует считать q₀. Согласно изложенному, начальное состояние автомата К^(p)[] является невозвратным – в процессе обработки любого входного слова, выйдя из этого состояния, автомат в него никогда не вернется. На рис.2.10 представлен конечный автомат К⁽³⁾[], распознающий числа, кратные трем (пустое слово, в язык, распознаваемый данным автоматом, не входит).

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

Любой конечный автомат с пустым множеством «хороших» состояний F распознает пустой язык. Любой конечный автомат, в котором каждое состояние «хорошее», распознает универсальный язык. Конечные автоматы, распознающие пустой и универсальный языки и имеющие только одно состояние, представлены на рис. 2.11 и 2.12 соответственно (x- произвольная буква алфавита A).

Сейчас предположим, что язык L конечен, пусть L={₁, ₂, ... , _p}. Диаграмму конечного автомата К(L), распознающего слова языка L, строим в виде дерева, корнем которого является вершина q₀, образующая нулевой уровень. В вершине q₀ реализуем ветвление (далее эта операция будет выполняться и для других вершин): проводим из данной вершины n дуг, над первой надписываем а₁, над второй – а₂, ... , над n-ой – а_n, концами этих дуг являются n вершин следующего (в данном случае – первого) уровня. Выполнив ветвление в каждой из вершин первого уровня, получаем n² вершин второго уровня; выполнив ветвление в каждой из вершин второго уровня, получаем n³ вершин третьего уровня, и т.д. Процесс продолжается до тех пор, пока не будут построены вершины r-го уровня, где r – число букв в самом длинном слове языка L. Операции ветвления в вершинах r-го уровня не выполняются; если на вход автомата, находящегося в некотором состоянии из r-го уровня, поступает еще одна буква, он переходит в неотображенное диаграммой отрицательно поглощающее состояние q_плох. Между вершинами-состояниями построенного r-уровневого дерева и имеющими длину не больше, чем r, словами алфавита А существует взаимно однозначное соответствие – каждому такому слову сопоставляется состояние, в котором оказывается автомат, обработавший, начиная от q₀, данное слово. Каждое отображенное в дереве состояние автомата К(L) называем именем соответствующего ему слова (состояние q₀ получает при этом имя пустого слова). Множество F «хороших» состояний автомата К(L) считаем следующим: ₁, ₂, ... _p. Построение распознающего язык L конечного автомата закончено. Теорема доказана полностью.

В приведенном доказательстве изложен универсальный алгоритм синтеза автомата, распознающего конечное множество слов. Отметим, что в конкретных задачах автоматы, распознающие те или иные конечные языки, нередко строятся существенно проще. На рис. 2.13 представлен автомат, распознающий конечный язык A={0, 01, 10, 001, 101, 1100}.

0