1 Зображення подій в автоматах Лекція 13

алфавітне відображення є автоматним. Розглянемо автоматні відображення та зв'язок між

автоматним відображенням і довільним алфавітним відображенням. Нехай відображення f задовольняє таким умовам:

будь-якому припустимому вхідному слову p(X) відображення f зіставляє вихідне слово f(p)(Y), що має однакову довжину зі словом p, |f(p)|=|p|;
якщо p – припустиме вхідне слово, а p1 – початковий відрізок слова p, то f(p1) існує та збігається з деяким початковим відрізком слова f(p).

Автоматні відображення (1)

будь-яке алфавітне відображення, що задовольняє цим умовам, є автоматним відображенням.
Будь-яке

алфавітне відображення може бути перетворене на автоматне шляхом введення до алфавітів X та Y порожньої літери e.
Однією із форм задання алфавітного відображення зі скінченною областю визначення є таблиця відповідності (словник).
Зручною формою задання будь-яких автоматних відображень є їх задання за допомогою подій.
Нехай X = {x1, ..., xm} – довільний алфавіт, а (X) – множина всіх слів у ньому. Будь-яка підмножина множини (X) називається подією в алфавіті X.

Подія в алфавіті

алфавітом

X = {x1, ..., xm} і вихідним алфавітом Y = {y1, ..., yn}, що індукує часткове відображення f множини (X) у множину (Y).

Означення 4.1. Подією Rj, що зображена в автоматі A вихідною літерою yj (jJ = {1, 2, ..., n}), називається множина всіх слів p(X) автомата, для яких слово f(p) визначене та закінчується літерою yj.

Якщо NY – деяка підмножина вихідних літер, то подією, що зображена в автоматі A множиною N, називається об'єднання подій, які представлені всіма елементами цієї множини. У випадку, коли N збігається з алфавітом Y, відповідна йому подія називається канонічною множиною подій R1, R2, ..., Rn автомата A.

Канонічна множина подій

множини (X) у множину (Y) довільного абстрактного автомата A із

вхідним X = {x1, ..., xm} і вихідним Y = {y1, ..., yn} алфавітами еквівалентне заданню канонічної множини подій R1, R2, ..., Rn автомата, що розглядається.

Із теореми випливає, що довільне автоматне відображення можна задавати за допомогою розбиття множини (X) усіх слів у вхідному алфавіті на скінченне число подій, що попарно не перетинаються. Для опису скінченних і деяких класів нескінченних подій розглянемо алгебру подій.

Задання автомата канонічною множиною подій

X називається множина всіх подій в алфавіті, на якій визначено

систему трьох операцій:

двох бінарних (диз'юнкція та множення),
та однієї унарної (ітерація (замикання Кліні)).

P, що позначається P = RS та утворюється теоретико-множинним об'єднанням

подій R і S.
Множенням подій R і S називається подія U, що позначається U = RS і складається з усіх слів, які мають вигляд u = rs, де uU, rR та sS. Таким чином, слова події U утворюються приписуванням праворуч будь-якого слова події S до будь-якого слова події R, але не навпаки, тобто операція множення не є комутативною.
Ітерацією події R називається подія, що позначається {R}* і визначається як диз'юнкція порожнього слова e, події R, події RR, події RRR і так далі до нескінченності, тобто {R}* = eRRRRRR...

Сигнатура операцій алгебри подій

x2}. Задано події R = {x1, x2x1} та S =

{x2x2, x1x2} в алфавіті X. Необхідно побудувати події RS, RS, {R}*.
RS = {x1, x2x1, x2x2, x1x2},
RS = {x1x2x2, x1x1x2, x2x1x2x2, x2x1x1x2},
{R}* = {e, x1, x2x1, x1x1, x1x2x1, x2x1x1, x2x1x2x1, x1x1x1, x1x2x1x1, x2x1x1x1, x2x1x2x1x1, x1x1x2x1, x1x2x1x2x1, x2x1x1x2x1, x2x1x2x1x2x1, ...}.

Події, що відрізняються одна від одної тільки порожнім словом e, вважаються такими, які не можна відрізнити. Крім події e розглядатимемо також порожню подію , яка складається із порожньої множини літер вхідного алфавіту.

Приклади подій. Порожня подія

xm} – довільний алфавіт. Введемо означення регулярного виразу в алфавіті

X, яке визначається рекурсивно (тобто означення є рекурсивним) у такий спосіб:
а) символи x1, ..., xm, e та  є регулярними виразами;
б) якщо R і S – регулярні вирази, то регулярними виразами є й RS, RS, {R}*;
в) жодні інші вирази, не одержані шляхом скінченного числа застосувань попередніх двох правил, не є регулярними.

Регулярний вираз є формулою в алгебрі подій, причому одна й та сама подія може бути по-різному виражена через одноелементні події та операції диз'юнкції, множення та ітерації.

Рекурсивне визначення регулярного виразу

вирази, називаються регулярними подіями. У протилежному випадку події називаються нерегулярними.

Звернемося

до деяких правил еквівалентних перетворень регулярних виразів. Спочатку розглянемо основні властивості операцій , , { }*, що випливають із визначень і сигнатури операцій алгебри подій. Нехай P, R, S – довільні регулярні події з (X). Тоді мають місце співвідношення:
P = P = P,
P = P= ,
Pe = e P = P,
{}* = e,
{e}* = e.

Регулярні події

{P}*P.

Асоціативність диз'юнкції та множення:
P(RS) = (PR)S;
P(RS) = (PR)S.

Ліва та права

дистрибутивність множення щодо диз'юнкції:
P(RS) = (PR)(PS);
(PR)S = (PS)(RS).

Еквівалентні перетворення регулярних виразів (1)

= P;
{{P}*}* = {P}*.
Диз'юнктивне поглинання ітерації:
{P}*P = {P}*.
Мультиплікативне поглинання ітерації:
{P}*{P}*

= {P}*.
Дужки { }* називаються ітераційними. Для вказівки на послідовність виконання операцій в алгебрі подій вводяться звичайні дужки. За відсутності звичайних дужок першими виконуються операції ітерації, далі – множення і в останню чергу – диз'юнкції.

Еквівалентні перетворення регулярних виразів (2)

максимальна кількість вкладених одна до одної пар ітераційних дужок. Наприклад,

вираз {x1{x2{x1}*x1}*x3}*x2 має циклічну глибину три. Усі скінченні вирази мають нульову циклічну глибину.

Під циклічною глибиною регулярної події розуміють мінімальну циклічну глибину регулярних виразів, що її представляють.

Циклічна глибина регулярного виразу

x2, x3}. Розглянемо деякі регулярні події:
універсальна подія, що складається з

усіх слів алфавіту X, і може бути записана у вигляді P = {x1x2x3}*;
подія, що містить тільки трилітерні слова алфавіту X, має вигляд:
R = (x1x2x3)(x1x2x3)(x1x2x3);
подія, що складається з усіх слів, в яких хоча б один раз зустрічається відрізок літер x1x2x1, може бути записана у вигляді S = {x1x2x3}*x1x2x1{x1x2x3}*;
подія, що складається з усіх слів, які починаються літерою x1 або x3, а закінчуються відрізком x1x2, має вигляд: T = (x1x3){x1x2x3}*x1x2;

Приклади регулярних подій (1)

слова, довжина яких кратна двом, виглядає так:
U = {(x1x2x3)(x1x2x3)}*;
подія, що

складається із таких слів, початком яких є літери x1 або x2, далі йде дволітерне слово з x2 або x3 і, врешті, закінчення містить, принаймні, одну літеру x1, записується так: Q = {x1x2}*(x2x3)(x2x3)x1{x1}*.

Із розгляду операцій , , { }* алгебри подій випливає, що всі скінченні події є регулярними. Застосування операції ітерації викликає появу нескінченних регулярних подій. Більшість нескінченних подій є нерегулярними.

Будь-який регулярний вираз можна зобразити у вигляді графа. Графи елементарних

регулярних виразів, що відповідають диз'юнкції xixj, множенню xixj та ітерації {xi}*, наведено нижче. Вершинам графа приписують номери із множини {1, 2, 3, ...}. У кожному графі регулярного виразу фіксуються вершина, що є початком (як правило, має номер 1), та вершини, які служать кінцем.

При використанні графів елементарних регулярних виразів можна індуктивно побудувати граф

як завгодно складного регулярного виразу. Наприклад, вираз

R = x1x3{x2x1}*x4{x1}*x2{x3}*

має вигляд, що показано на наступному слайді. Початковою вершиною є вершина 1, а кінцевими – вершини 3, 6 та 1. Кожному шляху у графі регулярного виразу від початку до будь-якого з кінців має відповідати послідовність вхідних літер, що належить регулярному виразу, який розглядається. І навпаки, кожна послідовність, задана регулярним виразом, визначає деякий шлях у графі регулярного виразу.

R = x1x3{x2x1}*x4{x1}*x2{x3}*

деякого вигляду, можуть виникати хибні послідовності, які не відповідають регулярному

виразу. Наприклад, виділений на графі шлях відповідає слову x3x4x2, що не належить регулярному виразу R. Виникнення хибних послідовностей можна запобігти введенням на графі порожніх стрілок, що означають миттєвий перехід з однієї вершини графа до іншої.
Наведемо систему правил, що визначають типи регулярних виразів, графи яких мають містити порожні стрілки.

Задання регулярних виразів у вигляді графів (4)

на графі регулярного виразу S вводяться у випадку добутку двох

або більшої кількості ітерацій, тобто, коли



де Ri – довільний регулярний вираз. Геометричну інтерпретацію цього правила при n = 3 показано нижче.

на графі регулярного виразу S, яке починається та закінчується ітераційними

дужками, вводяться у випадках:

S = {{P}*R}*;
S = {R{N}*}*;
S = {{P}*R{N}*}*,

де P, R, N – довільні регулярні вирази. Застосування правила показано нижче.

на графі регулярного виразу S вводяться у випадку диз'юнкції, якщо

хоча б один із диз'юнктивних членів починається з ітерації S = {R}*Q{P}*...Q,
де Q – регулярний вираз, що не містить ітераційних дужок. Правилу 3 відповідає граф, який наведено нижче.

на графі регулярного виразу S вводяться при множенні зліва на

диз'юнкцію, якщо хоча б один із диз'юнктивних членів закінчується ітерацією: S = (Q{P}*{R}*...Q)N.
Граф цього виразу показано нижче.

стрілок для виключення хибних шляхів у графах регулярних виразів є

повною. Виправлений граф для виразу (слайд 17) показано нижче (застосовується правило 3).

Повнота системи правил