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


 

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

44728. Gerund. Gerund clauses 63.5 KB
  Tsiolkovsky 18571935 Mnkind will not remin on erth forever. Tsiolkovsky ws selftught mn. The min problem Tsiolkovsky hd been working t for mny yers ws creting theory of interplnetry trvel. 1 It ws Tsiolkovsky who suggested the ide of multistge rocket nd of mnmde stellite which could serve s lbortory for studying the universe.
44729. Verbals 51.31 KB
  They do this with n efficiency pproching one hundred per cent s compred with mximum of bout one per cent of other lsers. Semiconductor lsers re sure to open up gret prospects for solving vrious scientific nd technicl problems. Clcultions nd experiments show tht lredy superhrd substnces dimonds rubies nd so on nd hrd lloys cn be worked profitbly by ruby lsers for exmple.
44730. Modals + Perfect Infinitives. Subjunctive Mood. Conditional Sentences 56.05 KB
  By closer observtion of the spectrum however we find tht the spectrum is crossed by n immense number of fine drk lines mounting to mny thousnds. When we investigte the drk lines in the spectrum of the Sun we find tht these correspond line by line to the spectr emitted in the lbortory by vrious elements iron clcium hydrogen etc. From this it follows tht the light from the Sun must hve gone through clouds of these toms somewhere nd in respect to such substnces s iron or clcium or most other elements this must hve hppened on the Sun...
44731. Emphatic Inversion 47 KB
  To get even one report from computer requires the prior ppliction of gret del of intensive skilled humn lbour. Given below re some fundmentls concerning computer opertions. Computers perform with gret speed nd ccurcy mny opertions tht up to now hve trditionlly been done only by humn lbour.
44732. Elliptic Sentences 33.81 KB
  It ws believed on theoreticl grounds tht gs should be nonconducting in the bsence of rdition provided tht the potentil grdient cross it ws not so high tht sprking could tke plce. Curiously enough experiments undertken to test this hypothesis showed tht smple of ir in closed vessel lwys exhibited smll electricl conductivity in spite of every precution to eliminte rdition nd prevent lekge long the insultors. Tht these explntions were not sufficient to ccount for the observed phenomen ws shown by the experiments of some scientists who in...
44733. Word Order in the Simple Sentence. Types of Questions. The Noun: the Category of Number. The Use of Articles. Present, Past, Future Simple (Active Voice) 56 KB
  Mn is lso the cretor of the innumerble spiritul tresures of mnkind: the wonderful works of rt literture nd science. The mchine system mde it possible to include science in production on lrge scle. We live in the epoch when science becomes direct productive force of society. spred of informtion of knowledge of science поширення інформації знань науки 12.
44734. Past Participle, Simple Tenses (Passive Voice); Pronouns: demonstrative, personal and possessive 37.5 KB
  Potentil nd Kinetic Energy The cpcity of body to perform work is clled its energy. This energy is designted potentil if it is due to the position of the body. Energy in this form is designted s kinetic. t this point the body possesses no potentil energy t ll for its distnce bove the ground is zero but it does hve kinetic energy becuse of its motion.
44735. Present Participle. Continuous Tenses (Active, Passive). Quantifiers: some, any, no, much, many, little, a little, few, a few 82 KB
  Prctice reding the following wordcombintions: Tken into ccount for exmple in order to in fct in the lnguge of science in everydy life connected with the ide of time stte of rest stte of motion from motion to rest in scientific sense of the word the force is pplied to result in no work the mount of performed work the product of the force by the distnce the bility to work different kinds of energy ll moving bodies to drive the wterwheels of turbines. TEXT 3 FORCE WORK ENERGY ND POWER In the lnguge of science few words...
44736. Perfect Tenses (Active, Passive). Numerals. Cleft sentences: it is (was)…that (who) 66.5 KB
  In our scientific ge there is generl belief tht ll science s it grows to perfection becomes mthemticl in its ides. It is generlly true tht in the development of lgebr three stges hve been pssed successively: verbl bbrevited nd symbolic. Verbl lgebr is chrcterized by the complete bsence of ny symbols except of course tht the words themselves re used in their symbolic sense.