Глава 4. Регулярные языки

Автоматы-распознаватели, рассмотренные в предыдущем пара­графе, способны распознавать наборы входных слов. Под входным словом, как и прежде, мы понимаем произвольную строку конечной длины, составленную из символов входного алфавита А. У таких автоматов одно или несколько состояний заранее объявляются заключительными. Считается, что автомат распознал слово, поданное ему на вход, тогда и только тогда, когда он завершил работу над этим словом в одном из своих заключительных состояний.

Множество всех слов, распознаваемых автоматом, мы назвали языком. Сам язык может быть как конечным, так и бесконечным, но в любом случае он состоит только из слов, распознаваемых соответствующим автоматом. Сразу возникает несколько вопросов. Например, как по таблице или диаграмме Мура конкретного автомата узнать, распознает ли он заданный язык? Какой язык распознается тем или иным автоматом? Существует ли автомат, который распознает данный язык? Чтобы отвечать на подобные вопросы, сначала надо выбрать способ четкого описания языка. Мы рассмотрим один из таких спосо­бов. Он основан на использовании операций сложения, умножения и итерации языков, с помощью которых из простейших конечных язы­ков строятся более сложные языки, в том числе и бесконечные.

Определение. Суммой языков L и L’ называется язык, который обозначается L + L' и получается объединением множеств L и L’. т.е.

L + L' = {w|w ϵ L ᴗ L'}.

Иными словами, сумма языков состоит из слов, принадлежащих хотя бы одному из языков L иL'. Поэтому L + L' = L’ + L.

Далее конкатенацией (или соединением) слов w и w' будем назы­вать слово ww', полученное приписываем справа слова w' к слову w. Например, конкатенацией слов bа и сbа будет слово bасbа. Из этих же слов можно получить слово сbаbа, которое является конкатенацией сbа и bа. В общем случае конкатенации ww' и w'w различаются.

Определение. Произведением языков L и L’ называется язык, ко­торый обозначается L·L' и получается в результате конкатенации всех возможных слов w и w', где w принадлежит языку L, а w' - языку L’. т.е.

L·L' ={ww’|wϵL, w’ ϵL’}.

Заметим, что язык L∙L’ как правило, отличается от языка L' · L, хо­тя некоторые слова могут принадлежать обоим произведениям.

Пример 1. ПустьL = {а, сb},L’ = {аb, bсb}. Тогда

L·L' = {ааb, аbсb, сbаb, сbbсb},

L'·L = {аbа, аbсb, bсbа, bсbсb}.

Слово аbсb принадлежит обоим языкам L·L' иL'·L.

Далее будем использовать следующие обозначения: L⁰ = {Λ}, где Λ - пустое слово L¹ = L, L² = L · L, L³ = L² · L,...,L^к = L^к-1 · L.

Определение. Итерацией языка L называется язык, который обо­значается L^* и получается в результате сложения бесконечного числа языков {Λ} +L + L² + L³ +... + L^к +..., т.е.

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

Пример 2. Найдем итерацию языков L = {а} и L' = {bс}. Согласно определению

L* = {Λ}+{а}+{аа} + {ааа}+... = {Λ, а, аа, ааа,...} = {аⁿ| п = 0,1,2,...},

(L’)* = {Λ} +{bс} + {bсbс} +... = {Λ, bс, bсbс,...} = {(bс)ⁿ|п = 0,1,2,...},

где (а)⁰ = (bc)⁰ = Λ.

Иногда язык удобнее задавать не в виде множества, перечисляя слова, как мы это делали ранее, а с помощью выражений (формул), в которые входят слова и знаки операций сложения, умножения и итера­ции. Например, для языков L и L', рассмотренных в примере 1, вместо записейL= {а, сb} и L' = {аb, bсb} можно использовать равенства L = а + сb, L'=аb+bсb. Тогда

L·L' = (а + сb)∙(аb + bсb) = а∙аb + а∙bсb + сb∙аb + сb∙bсb =

= ааb + аbсb + сbаb + сbbсb.

Здесь мы применили очевидные свойства операций сложения, умно­жения и конкатенации слов: (u + v)∙w = u∙w + v∙w, u∙(v+w)=u∙v+u∙w, u∙v=uv.

Итерацию языков L = {а} и L' = { bс} из примера 2 можно запи­сать следующим образом:

L* = Λ +а +а² + а³ +... + аⁿ +... = а*,

(L’)* =Λ + bс + (bс)² +... + (bс)ⁿ +...= (bc)*.

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

Пустое подмножество множества A*, как и всякое другое его подмножество, тоже считается языком. Этот язык мы будем называть пустым языком и обозначать символом пустого множества Ø. Очевидно, что для любого языка L верны равенства L + Ø = L и L· Ø = Ø. Значит, при всех натуральных значениях п выполняется Ø ⁿ = Ø. То­гда из определения операции итерации получаем

Ø*=Λ + Ø + ز+ س+... + Øⁿ+...=Λ.

Заметим также, что Λ* = Λ, поскольку Λⁿ=Λ и Λ+Λ=Λ

Пусть имеется алфавит A = {a₁, а₂,.... a_s}. Одноэлементные языки a₁, а₂,.... a_s, а также язык, содержащий только пустое слово Λ, будем называть элементарными языками.

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

Чтобы доказать регулярность какого-либо языка, надо записать его в виде так называемого регулярного выражения, т.е. формулы, в которой конечное число раз используются элементарные языки и зна­ки операций сложения, умножения и итерации. Поскольку количество регулярных выражений счетно, то число различных регулярных язы­ков не более, чем счетно. Всего же имеется континуум языков над фиксированным конечным алфавитом А, т.к. язык - это любое под­множество счетного множества А *. Следовательно, существуют и не­регулярные языки. Доказать нерегулярность языка, как правило, быва­ет очень сложно.

Пример 3. Рассмотрим несколько языков.

1) Конечный язык L₁ = {а, аb, аbс} является регулярным языком, т.к. его можно задать равенством L₁ = а + аb + аbс = а + а · b + а · b ·с = а·(Λ + b· (Λ + c)). Последнее полученное выражение является регулярным, поскольку оно содержит только простейшие языки а, b, с и Λ и конечное число знаков операций сложения и умножения. Этот пример показывает, что любое конечное множество слов образует регулярный язык.

2) Бесконечный язык L₂= { с, саbс, саbсаbс, саbсаbсаbс, ... } является регулярным, т.к. его можно задать разными регулярными выражениями: с ·(а· b ·с)^*, либо (с ·а· b)^* ·с. Этот пример свидетельствует о том, что один и тот же язык можно представить через различные регулярные выражения.

3) Бесконечный язык L₃, состоящий из всех слов конечной длины в алфавите A = {а, b, с}, включая и пустое слово, является регулярным языком, поскольку выполняется равенство L₃ = (а + b + с)*.

4) Бесконечный язык L₄ над алфавитом А = {а, b, с}, образованный словами, которые содержат хотя бы одну букву с, регулярен, т.к. он может быть задан равенством L₄ = (а + b + с)* · с · (а + b + с)*.

5) Бесконечный язык L₅ над алфавитом А = {0,1}, образованный всеми словами, кроме слов 0 и 11, регулярен, т.к. его можно задать регулярным выражением Λ 1 + 00 + 01 + 10 + (0 + 1)³ · (0 + 1)*.

6) Бесконечный язык L₆ = {1, 10, 101, 1010, 10100,...}, состоящий из всех начальных отрезков { a₁, a₁a₂, a₁a₂a_3,… } бесконечной последовательности (10100100010...), не является регулярным.

Рассмотрим ещё две операции над языками, не относящиеся к числу основных.

Определение. Пересечением языков L и L’ называется язык, который обозначается L∩L’ и состоит из всех слов, принадлежащих одно­временно обоим языкам L и L'.

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

Определение. Дополнением языка L в алфавите А называется язык, который обозначается и состоит из слов множества А*, не принадлежащих языку L.

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

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

Существует тесная связь между регулярными языками и конечными автоматами. Дело в том, что, с одной стороны, любой регулярный язык обязательно распознается некоторым конечным детерминированным автоматом (автоматом Мили). А с другой стороны, автоматы Мили способны распознавать только регулярные языки. Оба эти утверждения сформулированы в основной теореме теории автоматов (теореме Клини).

ТЕОРМЕМАКлини: Классы автоматных и регулярных языков совпадают.

ТЕОРЕМА (основная теорема теории автоматов). Язык L распознается конечным детерминированным автоматом тогда и только тогда, когда L -регулярный язык.

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

---

Дата добавления: 2015-11-30