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


 

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

42020. Факторы, влияющие на результат измерений. Основной постулат метрологии. Погрешность измерений. Точность, сходимость и воспроизводимость измерений 19.35 KB
  В метрологической практике при проведении измерений необходимо учитывать ряд факторов, влияющих на результаты измерения. Это — объект и субъект измерения, средство измерения и условия измерения.
42021. Обработка строк и символов 47 KB
  Варианты заданий С помощью текстового редактора создать файл содержащий текст длина которого не превышает 1000 символов длина строки текста не должна превышать 70 символов. С помощью текстового редактора создать файл содержащий текст длина которого не превышает 1000 символов длина строки текста не должна превышать 70 символов. С помощью текстового редактора создать файл содержащий текст длина которого не превышает 1000 символов длина строки текста не должна превышать 70 символов.
42022. Использование классов на примере работы с простыми геометрическими фигурами 40.5 KB
  Варианты заданий Треугольник задаваемый координатами вершин. Прямоугольник задаваемый координатами своих левойверхней и правойнижней вершин стороны параллельны осям. Треугольник задаваемый координатами вершин. Прямоугольник задаваемый длинами своих диагоналей и координатами центра стороны параллельны осям.
42024. Наследование классов. Разработка простейшего производного класса 28.5 KB
  Цель работы: Разработка простейшего производного класса. В функции min организовать ввод конкретных параметров объекта с клавиатуры создание объекта экземпляра класса тестирование всех его методов как старых так и новых в текстовом режиме с выдачей соответствующих сообщений. Организовать исходный текст в виде пяти исходных файлов: заголовочный с описанием класса .h из предыдущей части задания; с реализацией методов функцийчленов класса .
42026. Перегрузка операций и функций 58 KB
  Для всех заданий реализовать: а конструктор инициализирующий значения полей некоторыми значениями; б вывод данных на экран оператор . Необходимо корректное описание данного оператора в демонстрация всех операций должны быть реализована через пользовательское меню где пользователь выбирает действие вводит данные указывает тип данных если нужно и т. Реализовать: а сложение вычитание векторов операторы –; б умножение вектора на скаляр оператор ; в скалярное произведение векторов оператор ; г векторное произведение...
42028. Динамические структуры данных (списки, очереди, стеки, двоичные деревья) 56.5 KB
  Программа должна обеспечивать: начальное формирование данных о всех автобусах в парке в виде двусвязного циклического списка; при выезде каждого автобуса из парка вводится номер автобуса и программа удаляет данные об этом автобусе из списка автобусов находящихся в парке и записывает эти данные в список автобусов находящихся на маршруте; при въезде каждого автобуса в парк вводится номер автобуса и программа удаляет данные об этом автобусе из списка автобусов находящихся на маршруте и записывает эти данные в список автобусов...