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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Лекция: Регулярные выражения и регулярныемножества. Теорема Клини о совпадении классовавтоматных множеств и регулярных множеств.Лектор - доцент Селезнева Светлана НиколаевнаЛекции по “Дискретной математике 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.Регулярные множестваАвтоматность регулярных множествКонец лекцииРегулярность автоматных множеств.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций