Параграф 2. Перетин, об»єднання та доповнення скінченних автоматів та автоматних мов

Теорема 2.2. Клас регулярних мов замкнутий відносно основних теоретико - множинних операцій – об»єднання, перетину і доповнення.

Приводиться доведення конструктивно - викладаються алгоритми побудови відповідних автоматів. Нехай L ₁ і L ₂ - регулярні мови, які розпізнаються скінченними автоматами К ¹={ Q ¹, A, q ¹₀, g ¹, F ¹} і К ²={ Q ², A, q ²₀, g ², F ²} відповідно; вважаємо, що Q ¹={ q ¹₀, q ¹₁, q ¹₂ ,..., q ¹ _f} і Q ²={ q ²₀, q ²₁, q ²₂ ,..., q ² _h}. Автомат К ^È={ Q, A, q ₀, g, F ^È}, що розпізнає мову L1 È L2, будуємо таким чином. Вважаємо Q = Q ¹х Q ²; кожен стан автомату що конструюється містить дві компоненти, ліву і праву. Початковим станом нового автомата вважаємо (q ¹₀ ,q ²₀), а функцію переходів g визначаємо наступним чином:

g ((q ¹ _i,q ² _j) ,а_k)=(g ¹(q ¹ _i,a_k) ,g ²(q ² _j,а_k))

Очевидно, по першій компоненті автомат К ^È моделює дію автомату К ¹, а по другій компоненті – дія автомату К ². Вхідне слово a належить об»єднанню мов L ₁ і L ₂ тоді і тільки тоді, коли після його обрабки автомат К ^È опинеться в стані, у якому або перша компонента належить сукупності F ¹, або друга компонента належить сукупності F ².Таким чином слід покласти:

F ^È=(F ¹х Q ²)È(Q ¹х F ²).

Всі компоненти автомату К ^È визначені, його побудова закінчена.

Автомат К ^Ç={ Q, A, q ₀, g, F ^Ç}, що розпізнає мову L₁ Ç L₂, відрізняється від К ^È тільки останньою своєю компонентою. Слід покласти

F ^Ç =F ¹х F ².

Нехай К ={ Q, A, q ₀, g, F } – скінченний автомат, який розпізнає мову L. Довільне слово a з А* належить мові L ^с= А *\ L тоді і тільки тоді, коли після його обробки автомат К опиняється в стані, що не належить F. Тому автоматом, що розпізнає мову L ^с, являється скінченний автомат К ^с={ Q, A, q ₀, g, Q \ F }. Образно говорячи, для того, щоб отримати скінченний автомат, що розпізнає доповнення регулярної мови, треба в автоматі, що розпізнає вихідну мову, поміняти місцями «хороші» і «погані» стани.

Теорема довдена.

На рис. 2.14 представлено два скінченні автомати, що розпізнають мови L ₁ і L ₂. На рис. 2.15 и 2.16 зображені автомати, що розпізнають L ₁È L ₂ і L ₁Ç L ₂ відповідно.

На рис. 2.17 представлено автомат, що розпізнає мову L ₃, яка є доповненням до мови L ₂. На рис. 2.18 зображено автомат, що розпізнає різницю мов L ₁ і L ₂ (або перетин мов L ₁ і L ₃).

Зауважимо, що часто автомати, які розпізнають об»єднання і перетин мов, будуються суттєво простіше. Це пов»язано з тим, що деякі стани з множини станів Q = Q ¹х Q ² можуть бути недосяжними. Розглянемо наступний приклад. Нехай треба пбудувати автомат, який розпізнає об»єднання мов L ₁ і L ₂; автомати K ₁ и K ₂, що розпізнають ці мови, зображені на рис. 2.19.

Діаграмму переходів автомату K ^È (рис. 2.20), що розпізнає мову L ₁È L ₂, будуємо наступним чином. Вводимо вершину, яка відповідає початковому стану (q ₀¹, q ₀²). По букві a автомат K ₁ з стану q ₀¹ переходить в стан q ₁¹, а автомат K ₂ – з q ₀² в q ₁². Це означає, що автомат K ^È з стану (q ₀¹, q ₀²) перейде в стан (q ₁¹, q ₁²). Додамо в діаграму відповідну вершину і дугу, що веде в неї. Так як. по букві b автомат K ₁ переходит з q ₀¹ в q ₂¹, а автомат K ₂ – з q ₀² в q ₂², то автомат K ^È з стану (q ₀¹, q ₀²) перейде в стан (q ₂¹, q ₂²). Відповідна вершина і дуга додаються в діаграму. Розглянемо вершину (q ₂¹, q ₂²). По букві a автомат K ₁ з q ₂¹ переходить в q ₁¹, а автомат K ₂ – з q ₂² в q ₁², відповідно, автомат K ^È з стану (q ₂¹, q ₂²) перейде в стан (q ₁¹, q ₁²), який вже присутній на діаграмі. Тому в діаграму додається тільки відповідна дуга. По букві b автомат K ₁ залишається в стані q ₂¹, а автомат K ₂ переходить з q ₂² в q ₀², тому автомат K ^È по букві b з стану (q ₂¹, q ₂²) переходить в стан (q ₂¹, q ₀²). В діаграму додаються вершина (q ₂¹, q ₀²) і напрямлена в неї дуга. Розглядаючи далі вершини (q ₁¹, q ₁²) і (q ₂¹, q ₀²), ми виявимо, що нових вершин не виникає, в діаграму додаються лише дуги, що ведуть в уже існуючі вершини. «Хорошими» (заключними) будуть являтися стани (q ₂¹, q ₀²) и (q ₂¹, q ₂²).

Точно так само будується діаграма скінченного автомату K ^Ç, який розпізнає мову L ₁Ç L ₂ (рис. 2.21). Автомат K ^Ç відрізняється від автомату K ^È тільки множиною заключних станів.

Дата добавления: 2014-01-07