68836

Скінчені автомати, що приймають регулярні вирази

Лекция

Информатика, кибернетика и программирование

Побудова М7. Для побудови цього автомату використовується ідея приєднання виходу М1 до входу М2. Беремо Q7 = Q1  Q2, вважаючи, що Q1  Q2 =  , тобто усі стани автомату М1 відрізняються від станів автомату М2 незалежно від позначень. Множина заключних станів означається як...

Украинкский

2014-09-26

155 KB

1 чел.

Лекція 6

Скінчені автомати, що приймають регулярні вирази

Будемо казати, що скінчений автомат приймає  регулярний  вираз,  якщо автомат представляє мову, описану цим виразом.

    

                a 

 

                    a   

 

            a   

    

                 a    

                

Автомати, що приймають простіші регулярні вирази  , {}, {a | a   }, де   - вхідний  алфавіт,  зображені  на  рис.6.1,  а,  б,  в   відповідно.

                                                                           

                         а)                                        б)                                          в)                                

Рис.6.1. Автомати, що приймають простіші регулярні вирази.

             а) L(M) = ; б) L(M) = { };  в) L(M) = { a }.

Зауважимо, що другий автомат детермінований, а перший і третій - ні.

Лема 6.1. За поданими автоматами

М1  = (Q1, , 1, q, F1),  M2  = (Q2, , 2, p, F2)

можна побудувати автомати  М3 , ... , М8  такі, що

                                               L(M3) =  * \ L(M1),

                                               L(M4) = L(M1)       L(M2),

                                               L(M5) = L(M2) \ L(M1),

                                               L(M6) = L(M1)       L(M2),

                                               L(M7) = L(M1)L(M2),

                                               L(M8) = L*(M1).

Доведення  проведемо  конструктивним  шляхом,  тобто  побудуємо автомати  М3, ... , М8.

Побудова  М3. Автомат  М3  можна одержати з  М1  заміною  множини F1  заключних станів на множину   Q1 \ F1 . Отже,

M3  = (Q1, , 1, q, Q1 \ F1).

Побудова  М4. Візьмемо   Q4 = Q1 x Q2. Нехай   r  =  (q, p)  Q4.  

Означимо  4

                                                         4:  ((qi, pj), s) (1(qi, s), 2(pj, s))

та множину  F4

F4 = {(qi, pj)  |  qi  F1 &  pj  F2)}.

Тоді

M4 = (Q4, , 4, r, F4). 

 Побудова М5  прямує з побудови  М3  та  М4, оскільки

L(M4) \ L(M1) = L(M2) ( * \ L(M1)) = L(M2)  L(M3).

 Побудова М6  виконується подібно до  М4. Беремо  Q6 = Q4, 6  = 4,   а  

               F6 = {(qi, pj)  |  qi  F1  або  pj  F2)}. 

Тоді

  М6 = (Q6, , 6, r, F6).

 Побудова М7. Для побудови цього автомату використовується ідея  приєднання виходу  М1  до входу  М2. Беремо  Q7 = Q1  Q2,   вважаючи,   що Q1  Q2 = , тобто усі стани автомату  М1  відрізняються від станів  автомату  М2  незалежно від позначень. Множина заключних станів означається як

F7  = F2,

а функція переходів  7  означається таким чином

1)  7 :  ( qi, s ) qj,  якщо  1 :  ( qi, s )  qj  або  2 : ( qi, s ) qj;

2)  7 :  ( qi, s ) p,    якщо 1:  ( qi, s) qj,   &  qj  F1.

Тоді

М7 = (Q7, , 7, q, F7). 

Побудова  М8 . Цей автомат  будується  аналогічно  попередньому.

Спочатку для того,  щоб  М8  приймав  пустий  рядок =  L0 (M1),  уводиться початковий стан  u  Q1. Потім  Q8  та  F8  означаються як

Q8  = Q1  { u },  F8  =  F1  { u },

а  8  подібно до 7   означається таким чином

1) 8 :  ( qi, s )   qj,  якщо  1 :  ( qi, s ) qj;

2) 8 :  ( u, s )   qj,  якщо  1 :  ( q, s ) qj;  

3) 8 :  ( qi, s ) q,  якщо  1 :  ( qi, s ) qj  &   qj  F1.

Тоді 

М8 = (Q8, , 8, u, F8). 

                 x     

 

 y                  x                  y

                    M2

Приклад  побудови  автоматів   М3 … M8   для   поданих автоматів  М1  та  М2  (рис.6.2) показаний на рис.6.3.

              x                  x

             

               y                   y                  x

                                       y

                          M1  

Рис.6.2. Початкові скінчені автомати.

Автомати  М7, М8  недетерміновані, але  від  них  завжди  можна  перейти до еквівалентних детермінованих.  

З леми 6.1 та означення регулярної множини безпосередньо прямує 

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

Має місце і зворотне твердження.

Теорема  6.2.  Мова,  що   представляється   скінченим   автоматом,  є регулярною множиною.

Доведення. Нехай  M = (Q, , , q0,  F) - скінчений автомат, і G  = (Q, E) - його граф,  Q = (q0, q1, … , qn). Кожному вхідному рядку  s  відповідає  шлях  у  графі  G.  Задача  полягає  у  побудові  регулярного виразу, що описує усі шляхи з  q0   до  усіх  qj  F.  

               x                  x

             

               y                   y                  x

                                       y

                          M3  

               y

                       y               y

                    

              x           x      x        x   x    x

                  

                    y                    y

              y

                             

                            4

               y

                       y               y

                    

              x           x      x        x   x    x

                  

                    y                    y

              y

                             

                            M5

               y

                       y               y

                    

              x           x      x        x   x    x

                  

                    y                    y

            y

                             

                            M6

               

                    x                  y

                    

                    y

               y         x    y            x         x

                                         y

              x                x                  

                                                         y

                            M7

                        x

                   x                  x       y

                            y  y

                       

                            y                    

            y                            x

   x                              

                            M8

Рис.6.3. Складені автомати  M3M8.

Спочатку побудуємо регулярний вираз  Vij, що відповідає усім  шляхам  з вершини qi  у вершину qj. Очевидно, що будь-який шлях з qi у qj може проходити через деяку множину  A Q  проміжних  вершин.  У  окремому випадку, можливо,  А = , або   А = {qi}.  Будемо  будувати Vij, послідовно поширюючи  А. Почнемо  з   А0  =  .  Це  означає,  що  розглядаються шляхи без проміжних вершин. Усім таким шляхам з qi у qj (i  j) відповідає регулярний вираз  

V0ij =   sk ,

                                                                     sk  Eij 

де  Eij    - множина вхідних символів, що переводять автомат  з qi у qj. Якщо  Еij = (i  j), будемо вважати  V0ij =  .  Крім  того,  для  всіх  i  {0, 1, … , n}    V0ij.

 Далі перейдемо до побудови V1ij, що описує усі шляхи з qi у qj з можливою проміжною вершиною q0,  тобто  А1 = {q0}.  Після  цього  розглянемо  А2 = {q0, q1} і так далі до   Аn+1   =  {q0, q1, … , qn}. Очевидно, що вираз  Vn+1ij, якому відповідає Аn+1, описує усі шляхи з  qi  у  qj, тобто  Vn+1ij = Vij.

Для  того, щоб показати, що Vn+1ij - регулярний вираз,  скористаємося індукцією за кількістю проміжних вершин  k. Коли  k = 0, твердження очевидне. Вірність твердження для  k+1  при припущенні  його для  k  прямує з формули 

Vk+1ij    = Vkij  Vkik  (Vkkk ) Vkkj.

де  Vkik - вираз, що описує усі шляхи з  qi  у  qj  з можливим використанням проміжних вершин q0, q1, … , qk-1. Усі вирази у правій частині формули за припущенням індукції регулярні,  а  тому  і  ліва  частина є регулярний вираз.

Отримавши   вирази Vij для  усіх  пар  вершин,  можна  скласти  регулярний вираз для  L(M), а саме 

                     L(M) =   V0j,

                                                                              qj  F 

чим і завершується доведення теореми. 

Зв’язок між скінченими автоматами та регулярними граматиками

Теорема 6.3. Мова представляється скінченим автоматом тоді і тільки тоді, коли вона породжується регулярною граматикою.

Доведення. Для поданого скінченого автомату

M = (Q, , , q, F) 

завжди можна побудувати регулярну граматику

G = (N, T, P, S),

де  N = Q, T = , S = q, а множина продукцій  Р  визначається так: 

             1) X  sY P, якщо   : (X, s) Y; 

             2) X s   P, якщо   : (X, s) Z,  та  Z F;              

             3) S     P, якщо     L(M).  

Тепер неважко показати,  що  для  кожного  x  *  умова  x  L(M) виконується тоді і тільки тоді, коли  x  L(G). Очевидно, що коли  q  F, то  приймається автоматом  М  і  виводиться правилом  S    у   граматиці  G,  та навпаки.

Якщо  x  L(M),  і  | x | = n, то   x = s1 s2sn ,   si  , i = 1, 2, … , n,   і тому у графі автомату  М  існує шлях, показаний на рис.6.4. 

                                 

                                  s1                s2             s3               sn-1            sn              

Рис.6.4. Шлях у автоматі  М.

Показані на рис.6.4 стани  Аi  N  не обов’язково усі різні, і  B  F. За побудовою граматики  G 

{S s1A1,  A1  s2A2, … , An-2  sn-1An-1, An-1  sn} P,

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

.

Рис.6.5. Дерево виводу

Листя наведеного дерева утворюють рядок символів, що виводиться  з символу  S. Таким чином,   x  L(G), тобто  L(M)  L(G).  Проводячи  міркування у зворотному напрямку, аналогічно одержуємо L(G)  L(M), і тому  L(G) = L(M). Отже за поданим  автоматом  завжди  можна  побудувати еквівалентну регулярну граматику.  

Тепер треба показати, що  за  поданою  регулярною  граматикою завжди можна побудувати еквівалентний автомат. Візьмемо граматику 

                       G1  = (N1, T1, P1, S1)                       

і побудуємо автомат  M1  = (Q1, 1, 1, q1, F1) таким чином 

1 = T1, q1 = S1, Q1 = N1 {τ} {π},

де τ - стан, у який  потрапляє  автомат   М1,  коли  вхідний  рядок  виводиться граматикою  G1, а  π - стан, що відповідає кожному  рядку  x  L(G). Множину F1  означимо так

                                              1) F1 = { τ }, якщо    L(G1),

2) F1 = { τ, q1}, якщо   L(G1),

а функцію  1  -

1)   1 :   (X, si )  Y,  якщо  X siY P1, 

2)   1 :   (X, si )  τ,  якщо  X si  P1, 

3)   1 :   (τ, si )  π  для усіх  si  1, 

4)   1 :   (π, si )  π  для усіх  si  1,

5)  1 :   (X, si )  π,  якщо  X si  P1  і для усіх Y N1    X siY P1.

 Нехай рядок  x = s1 s2sk  виводиться у граматиці  G1, тоді  з  правил побудови  1  випливає, що у графі автомату  М1  існує  шлях  з  S  у  τ, який  М1  проходить, коли   x  надходить на вхід. Таким чином  М1  приймає  x.  

Навпаки, коли автомат  М1  приймає рядок   x,  то,  очевидно,  у  граматиці  G1  існує сукупність правил, що дає змогу вивести  x  з  S.  Отже  L(M1) = L(G1), а це і означає вірність теореми.

Треба зауважити, що стан  π  було уведено тільки для того,  щоб  означити поведінку автомату  М1  при надходженні рядка   x  L(G1).

Наприклад, нехай

G1 = ({S, A, B}, {a, b}, P, S),

де  Р  складається з продукцій

1. S aA

2. S bB

                                                                3. A a

                                                                4. B b                                

Тоді  L(G1) = {aa, bb}. Автомат  М1, означений як у теоремі  6.3,  під  дією  входу   а  переходить у стан  А, під дією входу  аа - у заключний  стан   τ,  а  під дією входу  аb - у стан  π. Якби не  було  стану  π,  вхід   ab  переводив   М1   у  пусту  множину  станів.  Таким  чином   стан  π  принципового значення не має.

На підставі теорем 6.1, 6.2 та 6.3 можна зробити  висновок,  що  класи мов,  що  описуються  регулярними  виразами,  або  представляються  скінченими автоматами,  або  породжуються  регулярними  граматиками,  співпадають. Ці мови називають регулярними.


 

А также другие работы, которые могут Вас заинтересовать

53243. Греция в XI-VI ст. до н.э 48.5 KB
  Развивать умения работать со схемами картами информационными текстами; делать самостоятельные суждения. методом рассказа учителя работа со схемой понятиями . Работа с картой. Рассказ учителя работа со схемой.
53244. Great Britain 94.5 KB
  This country is famous for its beautiful scenery: valleys, mountains, rivers. In the country there is the second highest mountain in Britain. In this country you can follow the narrow rocky paths in the Snowdonia National Park. What country is it? (Wales)
53245. РЕЛІГІЯ СТАРОДАВНЬОЇ ГРЕЦІЇ 32.5 KB
  Гестія богиня домашнього вогнища. Деметра богиня рильництва. Гера богиня заміжніх жінок. Арес бог війни Артеміда богиня полювання Афіна богиня мудрості Афродіта богиня кохання Аполлон бог сонця Піка богиня перемоги всіх богів записано на дошці і діти відмічають в зошиті Для того щоб зрозуміти як жили люди в давнину необхідно знати не тільки історичні події але й звички людей того часу їхні традиції релігію.
53246. Природа й населення Стародавньої Греції 84.5 KB
  Населення Давньої Греції та довколішніх земель. У різних містах Греції зустрілися у славетному храмі бога Аполлона в місті Дельори яке знаходиться поблизу південного схилу гори Парнас. Населення Давньої Греції та довколишніх земель.
53247. Викторина «Древняя Греция». 6 класс 62 KB
  Вспомните миф и назовите море. Назовите имя героини. Персефона Назовите сына критского мастера построившего лабиринт. Назовите героя.
53248. Греция в ІІ – первой половине І тыс. до н.э 62 KB
  Цели урока: познакомить учащихся с гомеровским периодом в истории Греции; рассмотреть произведения Гомера Одиссея Илиада и дать характеристику этим произведениям как литературным памятникам и историческим источникам; показать причины и направления греческой колонизации; формировать умения и навыки работы в группах со словарем и хронологической таблицей; повышать уровень культурного развития учащихся Ожидаемые результаты: после этого урока учащиеся смогут: называть время гомеровского периода и периода греческой колонизации в...
53249. Греко-перські війни 49.5 KB
  А Марафонська битва; Б Битва при Фермопілах; В Сала мінська битва; Г Остаточна перемога греків та її значення; Перший Афінський морський союз. А Марафонська битва; 13 вересня 490 до н. Марафонська битва 20000 персів та 11000 греків під керівництвом Мільтіада → перемога греків → марафонський біг 42 км. Б Битва при Фермопілах; 481 створено військовооборонний союз Спарти та Афін.
53250. Греко-перські війни 2.01 MB
  А Марафонська битва. Б Битва при Фермопілах. В Саламінська битва. А Марафонська битва.
53251. Греко-перські війни 52 KB
  А Марафонська битва; Б битва при Фермопілах; В Саламінська битва; 3. А Марафонська битва. Марафонська битва Б Битва при Фермопілах. битва при Фермопілах.