Операції в алгебрі подій

Назва роботи: Операції в алгебрі подій

Предметна область: Комунікація, зв'язок, радіоелектроніка та цифрові прилади

Опис: Диз'юнкцією подій S1 S2 Sk називають подію S = S1vS2vvSk, що складається з усіх слів, що входять у події S1 S2 Sk. Добутком подій S1 S2 Sk називається подія S = S1 S2 Sk що складається з усіх слів отриманих приписуванням до кожного слова події S1 кожного слова події S2 потім слова події S3 і т. слова входять у події S1S2 і S2S1 різні: т. що складається з порожнього слова e та всіх слів виду S SS SSS і т.д.

Дата завантаження: 2013-08-04

Розмір файлу: 24.5 KB

Роботу завантажили: 3 чол.

Операції в алгебрі подій.

Алгебра подій включає три операції:

диз'юнкцію (об'єднання) подій;
Добуток подій;
Ітерація подій.

Диз'юнкцією подій S1, S2, …, Sk називають подію S = S1vS2v … vSk, що складається з усіх слів, що входять у події S1, S2, …, Sk.

приклад. Подія S1 містить слова x1, x2x1, x1x1, тобто. S1 = (x1, x2x1, x1x1), а S2 = (x2, x1x2). Тоді S = S1vS2 = (x1, x2, x1x1, x1x2, x2x1).

Добутком подій S1, S2, ..., Sk називається подія S = S1 * S2 * ..., * Sk, що складається з усіх слів, отриманих приписуванням до кожного слова події S1 кожного слова події S2, потім слова події S3 і т.д.

приклад. S1і S2 ті самі. S = S1 * S2 = (x1x2, x1x1x2, x2x1x2, x2x1x1x2, x1x1x2, x1x1x1x2). Твір подій не комутативно, тобто. слова, що входять у події S1S2 та S2S1 різні: тобто. S1S2  S2S1 . Оскільки твір не комутативно, слід розрізняти операції «множення праворуч» та «множення зліва». Наприклад, щодо твору подій S1S2 можна сказати, що подія S2 помножена наподія S1справа, а подія S1на S2 зліва.

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

Ітерацією події S називається подія, що складається з порожнього слова e та всіх слів виду S, SS, SSS тощо. до нескінченності. Т. е. = e v S v SS v SSS v….

приклад. S = (x2, x1x2).

= (e, x2, x2x2, x2x2x2, …, x1x2, x1x2x1x2, …, x2x1x2, x1x2x2, …)

При синтезі кінцевих автоматів найважливішу роль грають регулярні події. Нехай дано кінцевий алфавіт X = (x1, x2, …, xm).

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

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

Теорема. Будь-які регулярні вирази і тільки вони представлені в кінцевих автоматах.

З цієї теореми випливає, що будь-який алгоритм перетворення інформації, який можна записати у вигляді регулярного вираження, реалізується кінцевим автоматом. З іншого боку, будь-які кінцеві автомати реалізують ті алгоритми, які можна записані як регулярних выражений.

Розглянемо, як можна зробити перехід від описової форми завдання алгоритмів роботи кінцевих автоматів до представлення цихалгоритмів у вигляді регулярних виразів. З метою спрощення такого переходу вводять основні події, у тому числі з допомогою операцій диз'юнкції, множення та ітерації можна скласти складніші події, відповідні заданому алгоритму роботи автомата. За основні події приймають такі події, які найчастіше зустрічаються в інженерній практиці синтезу схем ЦВМ.