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 можна зробити  висновок,  що  класи мов,  що  описуються  регулярними  виразами,  або  представляються  скінченими автоматами,  або  породжуються  регулярними  граматиками,  співпадають. Ці мови називають регулярними.


 

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

70331. Программирование на алгоритмическом языке Паскаль 644.5 KB
  Переменные снабжаются именами, которые могут содержать латинские буквы, цифры и знаки подчеркивания, но начинаться имя должно с буквы. Программист выбирает имена произвольно, но таким образом, чтобы они указывали на смысл переменной.
70332. Средневековая философия 1014.5 KB
  Ариане не принимали основной догмат официальной христианской церкви, согласно которому бог-сын единосущен богу-отцу. По учению Ария, сын божий Логос (Христос) — творение бога, следовательно, не единосущен ему, т. е. в сравнении с богом-отцом является существом низшего порядка.
70333. Словарь терминов по средневековым школам и университетам 95 KB
  Диспут (лат. disputatio) – в схоластической системе образования средневековой Европы формальный способ ведения спора, проводимого с целью установления богословской или научной истины. Данный процесс подчинялся формальным правилам, основными из которых были ссылки устоявшиеся...
70334. Терминология средневековой литературы 22.65 KB
  Канцона буквально песня лирическая форма средневековой поэзии возникшая первоначально в феодально-рыцарской лирике Прованса откуда она была усвоена французскими и итальянскими подражателями.
70335. СЛОВАРЬ ТЕРМИНОВ И ПОНЯТИЙ ПО ИСТОРИИ СРЕДНЕВЕКОВОГО ИЗОБРАЗИТЕЛЬНОГО ИСКУССТВА 2.61 MB
  Йоркский собор (англ. York Minster) — готический собор в английском городе Йорке, который оспаривает у Кёльнского собора звание самого большого средневекового храма на севере Европы. Строительство началось в 1220 году и продолжалось 250 лет. Собор славится самыми большими витражными окнами средневековой Европы.
70339. Средневековая музыка 651.8 KB
  Alternatim - техника «альтернативного» исполнения псалмов и (псалмоподобных) песней библейских (Benedictus, магнификат), а также строфических форм григорианского хорала. Начиная с позднего Средневековья, а особенно в эпоху Ренессанса и в барочной музыке один стих таких молитв...