Локальні автомати

Зміст

Опис [ред.]

Визначення:

Граф Майхілла [math]G[/math] (над алфавітом [math]\Sigma[/math] )(англ.Myhill graph) — орієнтований граф, що задовольняє властивостям:

Для кожної впорядкованої пари вершин [math]v[/math] і [math]u[/math] існує тільки одне ребро з [math]v[/math] в [math]u[/math].
Деякі вершини позначені початковими, а деякі кінцевими. Ребро може бути початковим і кінцевим.
Вершини позначені різними символами з кінцевого алфавіту [math]\Sigma[/math] , тобто ми можемо звертатися до вершини за символом.

Нехай [math]G[/math] - граф Майхілла над алфавітом [math]\Sigma[/math].

Символ [math]c \in \Sigma[/math] назвемо дозволеним, якщо їм позначена вершина, що є одночасно початковою та кінцевою.

Не порожній рядок [math]c_1c_2 \ldots c_n[/math] з [math]\Sigma^*[/math] довжиною не менше двох символів називається дозволеним, якщо символом [math]c_1[/math] відзначена стартова вершина, а символом [math]c_n[/math] — кінцева, і для всіх [math]1 \leqslant i \leqslant n - 1[/math] у [math]G[/math] існує ребро [math](c_i, c_) [/ Math] .

Мова [math]L(G)[/math] , що розпізнається графом Майхілла, складається з усіх дозволених рядків [math]\Sigma^+[/math] .

Покажемо, що графи Майхілла можуть бути представлені у вигляді автоматів. Нехай [math] \ mathcal = (S, \ Sigma, i, \ delta, T) [/ math] - ДКА.

Визначення:

Автомат [math]\mathcal[/math] називаєтьсялокальним(англ.local automaton,Glushkov automaton), якщо для будь-якого [math]c[/math ] з [math]\Sigma[/math] безліч [math]\[/math] містить не більшеодного елемента.

Визначення:

Локальний автомат [math]\mathcal[/math] називаєтьсястандартним локальнимавтоматом (англ.standard local automation), якщо в ньому немає переходу в початковий стан.

Таким чином, автомат є локальним, якщо для кожного [math]c[/math] з [math]\Sigma[/math] немає переходів, зазначених [math]c[/math] , або якщо всі вони ведуть один стан.

Покажемо, що граф Майхілла може бути перетворений на стандартний локальний автомат таким чином, що мова, яку він розпізнає, не зміниться.

Теорема:

Доказ:[math]\triangleright[/math]

Нехай [math]G[/math] - граф Майхілла. Побудуємо автомат [math]\mathcal[/math] наступним чином:

Додамо вершину [math]i[/math] в [math]G[/math] з ребрами від [math]i[/math] до кожної стартової вершини [math]G[/math]; відзначимо вершину [math]i[/math] як стартовий стан.
Зазначимо кінцеві вершини як термінальні стани.
Зазначимо кожне ребро результуючого орієнтованого графа символом, що стоїть у вершині, на яку воно вказує.

Переходи перетворюються так: По побудові стартовий стан перестав бути термінальним. Покажемо, що отриманий автомат закінчено. Ребра, що виходять зі стартового стану, позначені різними символами, тому що вони вказують на вершини, які, за властивістю 3, були відзначені різними символами у вихідному автоматі. Якщо ми розглянемо будь-який інший стан [math] s [/math] , то два переходи з [math] s [/math] можуть мати однакові мітки тільки в тому випадку, якщо в [math]G[/math] обидва орієнтовані ребра йдуть водну й ту саму вершину. Але цього може бути за властивістю 1. Тобто [math]\mathcal[/math] — ДКА. За побудовою є стандартним локальним автоматом. Тепер просто перевірити, що [math]L(\mathcal) = L(G) [/math] .

[math] \Leftarrow [/math]

Нехай [math] \mathcal = (S, \Sigma, i, \delta, T) [/math] - стандартний локальний автомат, стартовий стан якого не є термінальним. Побудуємо по ньому граф Майхілла так:

Відзначимо всі стани [math] \mathcal [/math] , крім стартового, [math] input [/math] символами, що стоять на ребрах, що входять до цих станів.
Зітріть всі мітки на ребрах [math] \mathcal [/math] .
Відзначимо всі стани [math] s [/math] як початкові вершини, якщо існує перехід з [math] i [/math] до [math] s [/math]
Зазначимо всі термінальні стани як кінцеві вершини.
Видалімо вершину [math] i [/math] і всі ребра, що виходять із неї.

Назвемо отриманий граф [math] G[/math] - він буде графом Майхілла по побудові. Легко перевірити, що [math] L(G) = L(\mathcal) [/math] .

[math]\triangleleft[/math]

Приклад [ред.]

Граф Майхілла, зображений на малюнку 1, може бути використаний для розпізнавання рядків над алфавітом [math]\Sigma = \[/math] . За визначенням, мова, що розпізнається даним графом, складається з непустих рядків, що починаються і закінчуються [math]a[/math] .

Недетермінований автомат малюнку 2 є локальним автоматом і розпізнає той самий мову.

Локальна мова [ред.]

Розглянемо мову, яка розпізнається стандартним локальним автоматом.

Визначення:

Мова [math]L \subseteq A^*[/math]називаєтьсялокальною мовою(англ.local language), якщо [math]L \setminus \varepsilon[/math] може бути описаний наступним чином: [math]\exists P , S \subseteq A, N \subseteq A^2: L \setminus \varepsilon = (P A^* \cap A^* S) \setminus A^* N A^*[/math] .

Іншими словами, непусте слово належить локальній мові, якщо воно починається з символу з [math]P[/math] , закінчується на символ з [math]S[/math] і не містить пари символів з множини [math]N [/ Math] .

Нехай [math]L = (P A^* \cap A^* S) \setminus A^* N A^*[/math] — локальна мова. Визначимо автомат [math]\mathcal[/math] наступним чином:

набір станів [math]Q = A \cup \< \varepsilon \>[/math] ,
початковий стан [math]\varepsilon[/math] ,
термінальні стани [math]S[/math] ,
[math]\delta(\varepsilon, a) = a[/math] якщо [math]a \in P[/math] і [math]\delta(a, b) = b[/math] якщо [math] ab \not\in N[/math] .

Якщо [math]L[/math] містить порожній рядок, то багато термінальних станів [math]\mathcal[/math] — [math]S \cup \< \varepsilon \>[/math] .

Твердження:

[math]\triangleright[/math]

Автомат є локальним оскільки кожного стану [math]s[/math] і будь-якого символу [math]a[/math] [math]\delta(s, a)[/math] або невизначена або дорівнює [math]a[/ math]. За побудовою автомат є стандартним. Покажемо, що [math]L(\mathcal) = L[/math]. Нехай [math]x = a_1 \ldots a_n \in L(\mathcal)[/math] . Тоді в автоматі є шлях:

[math]\varepsilon \xrightarrow a_1 \xrightarrow a_2 \ldots a_ \xrightarrow a_n[/math] .

Тут [math] a_n [/math] - термінальнестан, [math] a_n \ in S [/ math] . Перехід з [math]\varepsilon[/math] до [math]a_1[/math] визначений, тому [math]a_1 \in P[/math] . Для кожного [math]j: 1 \leqslant j \leqslant n - 1[/math] факт, що перехід [math]a_j \rightarrow a_[/math] існує, означає що [math]a_j a_ \not \in N[ / Math] . Отже, [math] x \ in L [/ math] .

Нехай [math]x = a_1 \ldots a_n \in L[/math] . Тоді [math]a_1 \in P[/math] , [math]a_n \in S[/math] і для кожного [math]j[/math] [math]a_j a_ \not \in N[/math] . Отже в автоматі існує шлях з початкового стану до термінального:

[math]\varepsilon \xrightarrow a_1 \xrightarrow a_2 \ldots a_ \xrightarrow a_n[/math] . Отже, [math]x \in L(\mathcal)[/math] .

[math]\triangleleft[/math]

Алгоритм Глушкова [ред.]

Опис [ред.]

Дано регулярне вираз [math] e [/ math]. Алгоритм Глушкова будує недетермінований автомат, який розпізнає мову [math]L(e)[/math], що розпізнається [math]e[/math]. Побудова відбувається за кілька кроків:

Лінеарізація регулярного вираження. Кожен символ з алфавіту, що міститься в регулярному виразі, перейменовується таким чином, що кожен символ міститься в новому регулярному виразі не більше одного разу. Нехай [math]A[/math] - вихідний алфавіт, [math]B[/math] - новий алфавіт.

Обчислення множин [math]P(e'), S(e'), N(e')[/math] , де [math]e'[/math] - лінеаризований регулярний вираз. [math]P(e')[/math] — безліч символів, з яких починається слово з [math]L(e')[/math] . [math]S(e')[/math] - безліч символів, на які закінчується слово з [math]L(e')[/math] і [math]N(e')[/math] - безліч парсимволів, що зустрічаються у слові з [math]L(e')[/math] . Більш формально: [math]P(e')=\[/math] , [math]S(e')=\[/math] , [math]N(e') =\[/math].

Обчислення множини [math]\Lambda(e')[/math] такого що [math]\Lambda(e')=\cap L(e')[/math] .

Обчислення локальної мови із заданими множинами та побудова по ньому автомата.

Делінеаризація, перейменування кожного символу з [math]B[/math] у відповідний символ з [math]A[/math] .

Приклад роботи [ред.]

Розглянемо регулярний вираз [math]e = (a(ab)^*)^* + (ba)^*[/math] :

Так як порожнє слово належить мові, то [math] \ Lambda (e') = \ [/ math] .

Автомат локальної мови [math]L'=P'B^*\cap B^*S'\setminus B^*(B^2\setminus N')B^*[/math] містить початковий стан, позначений як [math ]1[/math] , та стану для кожного з п'яти символів алфавіту [math]B=\[/math] .

У побудованому автоматі існує перехід з [math]1[/math] (відповідного порожньому рядку) у два стани з [math]P'[/math] , перехід з [math]a[/math] в [math]b[/ math] якщо [math]ab \in N'[/math] три стани [math]S'[/math] термінальні (як і стан [math]1[/math] ).

Отримаємо автомат для [math]L(e)[/math] , видаливши індекси, додані першому етапі.

Твердження: