1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 6
Текст из файла (страница 6)
Наконецчерез wk обозначим слово, которое читается вдоль участка пути, начинающегося в pkи заканчивающегося в q 0 . Очевидно слово w0 ∈ T (A), поскольку оно читается вдольучастка, не содержащего новых дуг. Для каждого 1 6 i 6 k заменим в i-ом участкеsisiдугу pi −→ri на дугу q0 −→ri из исходного автомата A (такая дуга существует по22Глава II. Конечные автоматы и формальные грамматикипостроению), в результате получим путь по дугам исходного автомата, который начинается в q0 , заканчивается в выделенном состоянии, и вдоль которого по-прежнемучитается слово wi . Следовательно, wi ∈ T (A).
Таким образом, w = w0 w1 . . . wk , гдевсе wi ∈ T (A), т. е. w ∈ (T (A))∗ .Замечание. В предыдущей теореме можно предложить прямое доказательство замкнутости автоматных языков относительно пересечения, а именно, если заданыдва д.к.а. A1 = hQ1 , A, δ1 , q01 , F1 i и A2 = hQ2 , A, δ2 , q02 , F2 i, то определим д.к.а. A1 × A2 ,который называется прямым произведением исходных автоматов, следующим образом: A1 × A2 = hQ1 × Q2 , A, δ, hq01 , q02 i, F1 × F2 i, где функция перехода δ(hq1 , q2 i, a) =hδ1 (q1 , a), δ2 (q2 , a)i для любых q1 ∈ Q1 , q2 ∈ Q2 , a ∈ A.
Несложно убедиться в том,что T (A1 × A2 ) = T (A1 ) ∩ T (A2 ).Теорема 6. Любой конечный язык является автоматным.Доказательство. а) Нетрудно построить в явном виде автоматы, распознающиеязыки ∅, {Λ}, {a}, где a — буква.б) Из (а) и теоремы 5 (конкатенация) следует, что любой язык вида {w}, где w— слово, является автоматным.в) Из (б) и теоремы 5 (объединение) следует, что любой непустой конечный языкявляется автоматным.Лемма 7 (о накачивании). Пусть L — автоматный язык. Тогда существует n > 1такое, что для любого слова w ∈ L, где |w| > n, существует представление в видеw = xyz, где y 6= Λ, |xy| 6 n и xy i z ∈ L для всех i > 0.Доказательство.
Пусть A — д.к.а. такой, что T (A) = L, и пусть n — число состояний автомата A. Рассмотрим произвольное слово w ∈ L со свойством |w| > n.Следовательно, можно представить w = s1 . . . sn sn+1 . . . sm , где si — буквы. Так какw распознается автоматом A, то существует путь по дугам A, начинающийся в начальном состоянии, заканчивающийся в выделенном состоянии, и вдоль которогочитается слово w.s1 ...H© i£xq- i -. . .¢£yqsn+1- i - . . . sn- i-. . . sm- id¢£¢zРассмотрим первые n переходов в этом пути, вдоль которых читаются первые nбукв слова w. Так как число состояний, пройденных на этом участке пути, равноn + 1, то существует хотя бы одно состояние q, которое встречается не менее двухраз.Пусть x — часть слова s1 .
. . sn , которая читается от начального состояния до первого попадания в состояние q; y — часть слова s1 . . . sn , которая читается от первогопопадания в состояние q до последнего попадания в состояние q; z — остальная частьw (см. рисунок). Тогда y 6= Λ и |xy| 6 n. Кроме этого, чтение подслова y начинается и заканчивается в состоянии q. Следовательно, этот участок можно удалить изнашего пути или пройти по нему произвольное количество раз. Отсюда заключаем,что слово xy i z ∈ T (A) для всех i > 0.Следствие 8.
Существуют неавтоматные языки.§ 7. Регулярные языки23Доказательство. Рассмотрим язык L = {am bm | m ∈ ω} над алфавитом {a, b}. Допустим, L — автоматный. Следовательно, существует n > 1 как в лемме о накачивании.Рассмотрим слово an bn ∈ L. Длина |an bn | > n. Следовательно, по лемме можно представить an bn = xyz, где y 6= Λ, |xy| 6 n и xy i z ∈ L для любого i > 0. Отсюда следует,что существует k > 1 такое, что y = ak , и слово x не содержит букв b. Следовательно,слово xz = an−k bn ∈ L, что невозможно, поскольку n − k < n. Таким образом, L неявляется автоматным.Замечание.
Лемма о накачивании является необходимым условием автоматностиязыка. Это условие является достаточно сильным и демонстрирует определеннуюограниченность вычислительных возможностей конечных автоматов. Например, какмы заметили, никакой конечный автомат не способен распознать язык {am bm | m ∈ω}. Однако несложно построить формальную грамматику, которая порождает этотязык.
Другими словами, не любую алгоритмически разрешимую задачу можно решить с помощью конечных автоматов. Тем не менее, язык конечных автоматов оказывается достаточным для алгоритмического описания многих важнейших классовзадач в различных разделах математики и приложениях.§ 7.Регулярные языкиВ этом параграфе будет предложен другой подход для описания класса автоматныхязыков. Будет доказано, что автоматные языки — это в точности те языки, которыеимеют «синтаксическое» описание в терминах регулярных выражений.Определение. Пусть A — конечный алфавит, не содержащий символов (, ), ∪, ∗.Определим по индукции множество регулярных выражений над алфавитом A:10 .
Множества ∅, Λ, a, где a ∈ A, являются регулярными выражениями.20 . Если α и β — регулярные выражения, то (αβ), (α ∪ β) и (α∗ ) тоже являютсярегулярными выражениями.Таким образом, слово в алфавите A∪{(, ), ∪, ∗ } называется регулярным выражением,если оно может быть получено конечным числом применений пунктов 10 и 20 .Определение. Схожим образом определим множество обобщенно регулярных выражений над алфавитом A:10 . Множества ∅, Λ, a, где a ∈ A, являются обобщенно регулярными выражениями.20 .
Если α и β — обобщенно регулярные выражения, то (αβ), (α ∪ β), (α∗ ) и (α)тоже являются обобщенно регулярными выражениями.Замечание. В дальнейшем мы будем опускать некоторые (в том числе внешние)скобки при записи обобщенно регулярных выражений, как это делается в обычнойалгебре, считая, что операции имеют следующий приоритет: α∗ — самая сильнаяоперация, далее идет α, затем следует αβ, а операция α∪β — самая слабая. Например,запись α∗ β ∪ βα на самом деле означает (((α∗ )β) ∪ ((β)α)).24Глава II. Конечные автоматы и формальные грамматикиОпределение.
Определим отображение L из множества всех обобщенно регулярныхвыражений над алфавитом A в множество всех языков над A следующим образом:L(∅) = ∅,L(Λ) = {Λ},L(a) = {a}, для любого a ∈ A,L(αβ) = L(α)L(β),L(α ∪ β) = L(α) ∪ L(β),L(α∗ ) = L(α)∗ ,L(α) = A∗ \ L(α).Определение. Язык L над алфавитом A называется (обобщенно) регулярным, еслисуществует (обобщенно) регулярное выражение α над алфавитом A такое, что L(α) =L.
При этом будем говорить, что выражение α задает язык L.Пример. Язык L = {w ∈ {0, 1}∗ | w содержит подслово 11} является регулярным,поскольку его можно задать регулярным выражением (0∗ ∪ 10)∗ 11(0 ∪ 1)∗ . Заметим,что для любого (обобщенно) регулярного языка существует бесконечно много (обобщенно) регулярных выражений, задающих его. Например, тот же язык L можнозадать регулярным выражением (0 ∪ 1)∗ 11(0 ∪ 1)∗ или обобщенно регулярным выражением ∅11∅.Теорема 9. Класс автоматных языков совпадает с классом регулярных языков.Доказательство. Сначала докажем, что любой регулярный язык автоматен. ПустьL — регулярный язык над алфавитом A.
Следовательно, найдется хотя бы одно регулярное выражение γ, которое задает L. Индукцией по длине выражения γ докажем,что L — автоматный.10 . Если γ является выражением вида ∅, Λ или a, где a ∈ A, т. е. L = ∅, L = {Λ}или L = {a}, то в силу теоремы 6 язык L является автоматным.20 . Если γ является выражением вида (αβ), (α ∪ β) или (α∗ ), где α, β — регулярные, то по индукционному предположению заключаем, что языки L1 = L(α)и L2 = L(β) — автоматные. Тогда L = L1 L2 , или L = L1 ∪ L2 , или L = L∗1соответственно.
В любом случае по теореме 5 получаем, что L автоматен.Теперь докажем, что любой автоматный язык регулярен. Пусть L — произвольный автоматный язык. Следовательно, существует д.к.а. A = hQ, A, δ, q1 , F i с состояними Q = {q1 , . . . , qn } такой, что T (A) = L. Докажем, что L — регулярный. Дляэтого определим для всех 1 6 i 6 n, 1 6 j 6 n и 0 6 k 6 n множество слов:R(i, j, k) = {w ∈ A∗ | w читается вдоль пути автомата A, которыйначинается в qi , заканчивается в qj и который в промежуткемежду ними не заходит в состояния qk+1 , qk+2 , . . .
, qn }.(Здесь термином «промежуток между qi и qj » мы называем множество всех состояний пути, исключая его начало qi и его конец qj . Напомним также, что пустое словоΛ по определению читается вдоль пути, который содержит только одно состояние ине содержит ни одной дуги.)§ 7. Регулярные языки25Заметим, что при k = n множество R(i, j, n) состоит в точности из всех слов,читаемых вдоль путей нашего автомата, идущих из qi в qj . Кроме этого, ясно, что[L = T (A) =R(1, j, n).qj ∈FТак как регулярные языки замкнуты относительно объединения, то достаточно доказать, что все R(i, j, k) регулярны. Докажем это утверждение индукцией по k.10 .
При k = 0 множество R(i, j, 0) — это все слова, читаемые вдоль одной дуги,ведущей из qi в qj . Возможны три случая. Если такая дуга существует и онапомечена символом a, то R(i, j, 0) = {a}. Если такой дуги нет и qi = qj , тоR(i, j, 0) = {Λ}. Если такой дуги нет и qi 6= qj , то R(i, j, 0) = ∅. По определениювсе такие языки регулярны.20 . Допустим, что утверждение доказано для k − 1, т. е. все языки R(i, j, k − 1)регулярны.
Рассмотрим произвольное слово w ∈ R(i, j, k), оно читается вдольпути, который начинается в qi , несколько раз (может и 0 раз) заходит в qk изаканчивается в qj . Если этот путь не заходит в qk , то вдоль него читается слово из R(i, j, k − 1), т. е. w ∈ R(i, j, k − 1). Если же этот путь заходит в qk , топусть u — подслово w, которое читается вдоль участка пути, начинающегосяв qi и заканчивающегося в первом попадании в состояние qk ; w1 — подсловоw, которое читается вдоль участка, начинающегося в первом попадании в qkи заканчивающегося во втором попадании в qk ; .
. . ; ws — подслово w, котороечитается вдоль участка, начинающегося в предпоследнем попадании в qk и заканчивающегося в последнем попадании в qk ; и, наконец, пусть v — подсловоw, которое читается вдоль участка, начинающегося в последнем попадании вqk и заканчивающегося в qj .qii -. .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
