10. Регулярные выражения и регулярные множества. Теорема о совпадении классов регулярных множеств и автоматных множеств (Лекции)

Лекция: Регулярные выражения и регулярныемножества. Теорема Клини о совпадении классовавтоматных множеств и регулярных множеств.Лектор - доцент Селезнева Светлана НиколаевнаЛекции по “Дискретной математике 2”.1-й курс, группа 141,факультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suРегулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярные выраженияОпределим по индукции регулярные выражения надконечным алфавитом A.Базис индукции:1) ∅ – регулярное выражение;2) a, где a ∈ A, – регулярное выражение;3) Λ, где Λ ∈ A∗ – пустое слово, – регулярное выражение.Индуктивный переход: пусть s и t – регулярные выражения.Тогда1) s + t – регулярное выражение;2) st – регулярное выражение;3) (s)∗ – регулярное выражение.Других регулярных выражений нет.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествМножества, определяемые регулярными выражениямиКаждое регулярное выражение в алфавите A определяетнекоторое множество (язык) L ⊆ A∗ .Базис индукции:1) регулярное выражение ∅ определяет пустое множество ∅;2) регулярное выражение a, a ∈ A, определяет множество {a};3) регулярное выражение Λ, где Λ ∈ A∗ – пустое слово,определяет множество {Λ}.Индуктивный переход: пусть регулярные выражения s, tопределяют соответственно множества S, T ⊆ A∗ .

Тогда1) регулярное выражение s + t определяет объединение S ∪ T ;2) регулярное выражение st определяет произведение ST ;3) регулярное выражение (s)∗ определяет итерацию S ∗ .Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярные множестваМножество L слов в конечном алфавите A называетсярегулярным множеством (языком), если оно определяетсянекоторым регуляным выражением.Заметим, что одно и то же регулярное множество можетопределяться разными регулярными выражениями.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествПримерыПример 1.

Пусть A = {0, 1}.1. Регулярное выражение 01 обозначает множество {01},содержащее одно слово α = 01.2. Регулярное выражение (0 + 1)∗ 011 обозначает множествовсех слов из нулей и единиц, оканчивающихся на 011.3. Докажем, что множество всех слов из нулей и единиц,которые содержат две единицы подряд, является регулярным.Заметим, что это множество задается регулярным выражением(0 + 1)∗ 11(0 + 1)∗ .Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествТеорема 1. Пусть A – конечный алфавит. Каждое регулярноемножество L ⊆ A∗ является также и автоматным множеством.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство.

Пусть A = {a1 , . . . , an }.Докажем сначала автоматность множеств ∅, {Λ} и {ai },i = 1, . . . , n.Для доказательства построим диаграммы переходов ДКА безвыхода, которые принимают перечисленные множества.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество ∅:Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество ∅:f∗'$'$a,...,aa1 , . . .

, an1nq1q2&% &%Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество {Λ}:Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество {Λ}:∗f'$'$a1 , .

. . , ana1 , . . . , an -q1q2&% &%Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество {ai }:Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). ДКА без выхода,принимающий множество {ai }:∗'$'$a1 , . .

. , anA \ {ai } -q1q2f&%&%'$@ aia1 , . . . , an@R@ q3&%Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествАвтоматность регулярных множествДоказательство (продолжение). Кроме того, мы ужедоказали, что операции объединения, произведения и итерациисохряняют автоматность множеств.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествТеорема 2. Пусть A – конечный алфавит.

Каждое автоматноемножество L ⊆ A∗ является также и регулярным множеством.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство. Пусть A = {a1 , . . . , an }. Множество L –автоматное, значит найдется такой ДКА без выходаA = (A, Q, ψ, q1 , F ),что L = L(A).Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство (продолжение). Пусть Q = {q1 , .

. . , qr }. Неограничивая общности рассуждений, пусть F = {qr }.Определим множества Zijk , Zijk ⊆ A∗ , как множества слов валфавите A, по которым КА без выхода A из состояния qiпереходит в состояние qj , проходя только через состоянияq1 , . . . , qk .Т.е.Zijk= {α ∈ A∗ | ψ̄(α, qi ) = qj , ψ̄(β, qi ) ∈ {q1 , . . . , qk },α = βγ, β, γ ∈ A∗ , β, γ 6= Λ}.Докажем индукцией по k, что каждое из множеств Zijk являетсярегулярным.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство (продолжение).Базис индукции: k = 0.

Множества Zij0 состоят из всех слов валфавите A, которые переводят КА A из состояния qi всостояние qj , не проходя через промежуточные состояния.Если i = j, то Zii0 содержит пустое слово Λ и все слова валфавите B ⊆ A, гдеB = {a ∈ A | ψ(a, qi ) = qi }.Если i 6= j, тоZij0 = {a ∈ A | ψ(a, qi ) = qj }.Значит, Zij0 – регулярны.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство (продолжение).Индуктивный переход: Пусть множества Zijk регулярны.Рассмотрим множества Zijk+1 . Оно содержит все слова валфавите A, которые переводят КА A из состояния qi всостояние qj , проходя только через состояния q1 , . . .

, qk , qk+1 .Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство (продолжение).Пусть α ∈ Zijk+1 , т.е. ψ̄(α, qi ) = qj . Посмотрим, какиепромежуточные состояния проходит КА A при чтении слова α:1) если КА A не проходит через состояние qk+1 , то α ∈ Zijk ;2) если КА A проходит через состояние qk+1 , то слово αможно разбить на такие слова β, γ1 , . . . , γt , δ ∈ A∗ , чтоα = βγ1 . .

. γt δ, иkkkβ ∈ Zi(k+1), γ1 , . . . , γt ∈ Z(k+1)(k+1), δ ∈ Z(k+1)j.kkkПолучаем, Zijk+1 = Zijk ∪ Zi(k+1)(Z(k+1)(k+1))∗ Z(k+1)j.Т.е. Zijk+1 – регулярное множество.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествРегулярность автоматных множествДоказательство (продолжение). Осталось заметить, чтоr .L = Z1rРегулярные множестваАвтоматность регулярных множествРегулярность автоматных множествТеорема КлиниТеорема 3 (Клини).

Пусть A – конечный алфавит. Классавтоматных множеств в алфавите A совпадает с классомрегулярных множеств в алфавите A.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествПримерыПример 2. Пусть A = {0, 1}.1. Доказать, что множество L1 слов в алфавите A четнойдлины является автоматным множеством. Заметим, чтомножество L1 задается регулярным выражением(00 + 01 + 10 + 11)∗ .Значит L1 – автоматное множество.2.

Доказать, что множество L2 всех слов в алфавите A, кромеслова 01, является регулярным множеством. Заметим, чтоL2 = A∗ \ {01}. Множества A∗ и {01} – автоматные множества,разность автоматных множеств – также автоматное множество.Значит, L2 – регулярное множество.Можно найти регулярное выражение, определяющее множествоL2 :Λ+0+1+00+10+11+(000+001+010+011+100+101+110+111)(0+1)∗ .Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествЗадачи для самостоятельного решения1.

Какие множества в алфавите A = {0, 1} определяютследующие регулярные выражения:1) (0 + 11) ∗ 1;2) 10∗ 1(0 + 1)∗ 1?2. Найдите регулярные выражения, определяющие следующиемножества:1) множество слов из нулей и единиц, содержащих и подслово00, и подслово 11;2) множество слов из нулей и единиц, не содержащих ниподслово 00, ни подслово 11.Регулярные множестваАвтоматность регулярных множествРегулярность автоматных множествЛитература к лекции1.

Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.Регулярные множестваАвтоматность регулярных множествКонец лекцииРегулярность автоматных множеств.