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


 

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

23618. Методы передачи данных канального уровня 172.5 KB
  Канальный уровень оперирует кадрами данных и обеспечивает синхронизацию между приемником и передатчиком на уровне кадров. В обязанности приемника входит распознавание начала первого байта кадра, распознавание границ полей кадра и распознавание признака окончания кадра.
23619. Предмет и задачи лексикологии 238 KB
  Лексика совокупность слов как обозначений предметов явлений и понятий образующая словарный состав данного языка. Лексикологию интересует слово как: 1 словарная единица 2 имеющая определенное лексическое значение 3 имеющая предметное значение 4 обладающая системой словоизменительных форм. В отличие от фонетики фонемный состав и грамматики принадлежность к частям речи и роль в предложении лексикологию интересует предметное содержание слова лексическое значение. Частная исследует словарный состав одного языка.
23621. Программа по общей морфологии 85 KB
  : Наука 1988 Гл.: Наука 1977.: Наука 1968 Гл.: Наука 1973 с.
23622. Философия и филология 120 KB
  Автономова о российских дискуссиях 90х годов [1] Дискуссии очные и заочные по поводу взаимоотношений философии и филологии не случайно стали актуальными в современной России: в них ярко отображаются некоторые важные особенности интеллектуальной жизни. О филологической философии. Интересную точку зрения на взаимоотношения философии и филологии предложил А. Но филология вскоре забыв о том чем была обязана философии стала все тексты воспринимать и описывать как свои.