68835

Скінчені автомати

Лекция

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

На вхід автомату надходять рядки символів вхідного алфавіту. Кожний черговий символ призводить до того що стан автомату змінюється згідно з функцією а на виході зявляється символ що відповідає функції. Приклад умовного зображення автомату для обчислення суми двох двійкових чисел наведено...

Украинкский

2014-09-26

106.5 KB

5 чел.

Лекція 5

Скінчені автомати

Скінчений  автомат  -  це  модель  обчислювальної  машини,   що відображає скінченність оперативної пам’яті.

Означення  5.1.   Скінченим   (детермінованим)   автоматом  М  називається алгебраїчна структура

M = (Q,  , , , S, F, ),

де  Q - непуста множина станів;   - скінчений вхідний алфавіт; - скінчений вихідний алфавіт;  : Q x   Q  -  функція  переходів;  S - початковий стан; F (F       Q) - множина заключних станів;  : Q x    - функція виходів.  

На вхід автомату надходять рядки символів  вхідного  алфавіту. Кожний  черговий  символ  призводить  до  того,  що  стан   автомату змінюється згідно з функцією , а на виході з’являється символ, що відповідає функції . До  сприймання  першого вхідного символу автомат знаходиться у стані  S. Деякі   стани   помічаються  і називаються заключними.

Приклад умовного зображення автомату  для  обчислення  суми  двох  двійкових  чисел наведено на рис.5.1.

                       (1,1);0

                       (0,0);1        

     (0,1);1                             (0,1);0

     (1,0);1                             (1,0);0

     (0,0);0                             (1,1);1

Рис.5.1. Автомат для обчислення суми двох двійкових чисел.

Для  цього  автомату  Q = {q0, q1},   вхідний алфавіт складається з пар значень розрядів доданків -  = {(0,0), (0,1), (1,0), (1,1)}, вихідний алфавіт утворюється значеннями розрядів суми - = {0, 1}. На вхід надходять послідовності пар  двійкових цифр, що є значеннями  розрядів  двох  чисел,  суму  яких  обчислює  автомат. Пари цифр  надходять  послідовно, починаючи з молодшого  розряду.

Стани на малюнку  показано  подвійними  колами.  Обидва  стани є  заключні.  На  відміну  від  заключних  інші  стани  будемо  позначати одинарними колами. Переходи між  станами  показані  за допомогою  дуг,  біля яких  записані  відповідні значення вхідних символів (у дужках) та  вихідних  (після  крапки з комою).  Стрілочка,  що  не  виходить  із  стану  автомату,  показує на початковий стан  q0.  Таке  зображення  називається  уявленням  автомату у  вигляді  графа.  Вершини  графа  взаємно однозначно відповідають станам, а дуги - переходам.

Неважко  переконатись,  що  на   виході   автомату   послідовно  з’являються розряди суми, якщо врахувати,  що  стан  q0  відповідає  відсутності одиниці переносу, а  q1  - її наявності.

Означення  5.2.  Скінченим   розпізнавачем   або   акцептором  називається скінчений автомат без функції виходів.

Надалі при вивченні задачі аналізу будемо розглядати тільки автомати без виходів,  і  тому,  користуючись терміном скінчений автомат, завжди будемо мати на увазі  скінчений  розпізнавач.  Будемо  також  використовувати  для  них  позначення 

M = (Q, , , S, F).

Скінчені автомати застосовуються для  з’ясування,  чи  належить  поданий рядок символів до деякої мови. Якщо після читання  всіх  літер  вхідного рядка автомат опиняється в одному з  заключних  станів,  то  кажуть, що автомат приймає  рядок. В іншому разі  -  не приймає.  Кажуть, що мову можна представити за допомогою скінченого автомату,  якщо  існує скінчений автомат, що приймає рядок тоді і тільки  тоді,  коли  останній є реченням поданої мови.

Розглянемо приклад скінченого автомату

M = (Q, , , S, F),                        

де   Q = {A, B}; = {0, 1}; S = A; F = A,                

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

(A,0) = A;    (A,1) = B;    (B,0) = B;     (B,1) = A.

При читанні рядка  01001011  автомат послідовно  знаходиться  у  станах

А, А, В, В, В, А, А, В, А,

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

А, А, А, В, А, В,

не приймається.

Проаналізувавши функцію переходів, можна зробити  висновок,  що  оскільки стан автомату змінюється тільки при одиниці на вході, поданий  автомат  приймає  будь-який  рядок  з  нулів  та  одиниць,  у  якому  міститься парна кількість одиниць.

Функцію переходів можна задати за допомогою таблиці  переходів, стовпці якої відповідають станам, а рядки - входам. На  перетинанні  i-го рядка та   j-го  стовпця  записують  стан,  у  який  переходить  автомат з  i-го стану при j-му вході. Для  поданого  автомату таблиця  переходів зображена на рис.5.2,а, а граф - на рис.5.2,б.

    

                            1                                  

 

                            1        

      0                                   0

     

        стани                         

 входи

A

B

0

A

B

1

B

A

                                    а                                                                б

Рис.5.2. Скінчений автомат  М: а - таблиця переходів; б - граф.

Недетерміновані автомати

Наведене вище означення автомату вимагає, щоб стан, у який переходить автомат при будь-якому вході, визначався  однозначно. Такий  автомат  називається  детермінованим.  Якщо   при   означенні  автомату відображення має вигляд 

: Q x     P(Q),

де   P(Q) - множина підмножин станів, то автомат називається  недетермінованим.

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

M1  = (Q1, 1, 1, S1, F1),

де  Q1  = {A,  B},  1 = {0, 1},  S1 = A,  F1 = {B},             

а  1  визначається так 

         1 (A,0) = ,  1(A,1) = {A,B},   1(B,0) = {B},   1(B,1) = {B}.     

    

                           1

      1                                  1,0

Таблицю переходів та граф цього автомату зображено на рис.5.3.

    стани

входи

A

B

0

B

1

{A,B}

B

 

                               а                                                                    б

Рис.5.3. Таблиця переходів (а)  та граф (б) автомату  М1 .

Означення 5.3. Про  недетермінований  автомат  кажуть, що він  приймає рядок, якщо для даного рядка існує послідовність станів,  що  визначається згідно з , і закінчується заключним станом.

Таким чином, для того, щоб перевірити, чи приймається  вхідний  рядок  недетермінованим  автоматом, у найгіршому випадку треба продивитись усі можливі варіанти поведінки автомату. Наприклад, для  вхідного рядка  11 і автомату  М1  існують такі послідовності станів 

1) А, А, А;  2) А, А, В; 3) А, В, В.

Тому рядок  11  автоматом М1 приймається. Взагалі будь-який рядок, що починається з  1,  автоматом  М1   приймається, а рядок,  що  починається символом  0 - ні. При першому вхідному символі  0  стан  автомату  М1  не  визначений,  і  тому  при  вхідному рядку, що  починається з нуля, автомат потрапити у стан  В  не може.

Існує детермінований автомат  М2, що представляє ту саму мову, що і  М1:

М2  = (Q2, 2, 2, S2, F2),

де  Q2 = {A, B, C},    2 = {0, 1},  S2 = A,  F2  = {B}, і 2 визначається згідно з рис.5.4.

    

                           1

                  0

  1.                                             0,1

                   0,1

    стани

входи

A

B

C

0

C

B

C

1

B

B

C

                           

                              а)                                                                   б)

Рис.5.4. Таблиця переходів (а) та граф (б) автомату  М2.

    Для розпізнавання вхідного рядка за допомогою детермінованого автомату   повернення не потребуються (на відміну від недетермінованого), і це означає, що  час розпізнавання (кількість  необхідних операцій) є величина, пропорційна довжині входу.

Еквівалентність детермінованих та недетермінованих автоматів

Можна довести, що для кожного  недетермінованого  автомату, що  представляє мову  L, існує детермінований автомат, що представляє  L. Доведення базується на заміні підмножин  станів  недетермінованого  автомату новими станами детермінованого.

Нехай є недетермінований автомат

М = (Q, , , q0, F),

і вхід

s    *,  s = s1 s2 … sn.

Визначимо функцію  T(s), що відображає входи у множини станів автомату  М, таким чином

T() = {q0},   T(psi) =           (q,si),

де  p = s0 s1 … si-1 ,  1   i n,  s0 = .              

Згідно з означенням  функції  T, якщо  T(s)  F  , то рядок  s  приймається автоматом  М; тому мова L(M), що представляється  автоматом  М, може бути подана у вигляді 

L(M) = {s | T(s) F   }.

Теорема 5.1.  Для  будь-якого  недетермінованого  автомату М1 існує детермінований автомат  М2  такий, що  L(M1) = L(M2).                           

Доведення. Нехай 

M1 = (Q1, 1, 1, q0 , F1),   M2  = (Q2, 2 , 2, q0, F2).

Будемо вважати, що  1  =  2 = . Означимо стани автомату  М2  як множини станів автомату  М1, тобто  

Q2    P(Q1).

Покладемо  q0 = {q0} і розглянемо  множину  1(q0, s1)  усіх станів, у які переходить автомат  М1   зі  стану  q0  при вході  s1  

1(q0, s1) = {qi |  1 :  (q0, s1)   qi },    s1   .

Назвемо цю множину образом  (q0, s1) для функції   2 , тобто

2(q0, s1) = { 1(q0, s1)}  Q2,

і це означає, що множина станів  1(q0,s1) утворює один стан  автомату  М2 .

Якщо наступний вхідний символ  s2, то автомат  М1  переходить  у  один зі станів, що належить до множини 

1(qi,s2).

Цій множині ставиться у відповідність інший стан автомату М2  і  т.д.  У  загальному випадку можна записати 

2: ({qi1 , … , qik}, si )  {        1 (qij ,si )}.

Оскільки  Q1  скінчена множина, то Q2  теж скінчена.

Стан автомату  М2  будемо вважати заключним тоді і тільки  тоді, коли він містить заключний стан автомату  М1:

{qi1 , … , qik }  F2       m | 1  m  k  & qim  F1.

Скористаємося означенням функції  Т  для обох автоматів:

T1() = {q0},   T1(psi) =          1(q,si),

T2() = {q0},   T2(psi) =          2(q,si),

де  T2 (p) = {q}, тобто складається тільки з одного стану автомату M2.

Для того, щоб довести, що  L(M1) = L(M2), достатньо  показати, що для кожного  s  *  має місце 

T1(s)  F1         T2(s)  F2   .       (5.1)

З означення  F2  прямує, що співвідношення  (5.1)  виконується,  якщо  Т1(s)  та Т2(s) не містять різних станів  автомату  М1, тобто 

{… , qi , …} = T1(s) {{…, qi , …}} = T2(s).     (5.2)

Саме співвідношення  (5.2) і будемо доводити.

Зробимо це за допомогою індукції за довжиною  s. Якщо

|s| = 0, то  s = , і  T1() = {q0},  T2() = {q0} = {{q0}}.

Припустимо, що  відповідність має  місце  для  усіх  рядків  p  таких, що  |p|   n-1,  і  розглянемо  рядок   psn.  За  припущенням  індукції 

{… , qi , …} = T1(p) {{…, qi , …}} = T2(p).

Однак тоді, якщо  qj  1(qi,sn),  то  qj  T1(psn)  і за  означенням   2

{… , qj , …}  2({…, qi , …},sn) = T2(psn). 

З означень  T2  та  2  прямує, що   всі  елементи  з T2(psn)  можна  отримати таким же чином; тому

{… , qi , …} = T1(psn) {{…, qi , …}} = T2(psn).

А це означає, що для будь-якого  s  *  T1(s)  і T2(s)  не  містять  різних станів  автомату М1, і тому

L(M1) = {s | T1 (s) g F1   } = {s | T2(s) g F2   } = L(M2}.

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


 

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

2768. Дорожно-транспортное происшествие 44.42 KB
  Дорожно-транспортное происшествие. Травматизм при дорожно-транспортных происшествиях (ДТП) – одна из наиболее частых бед, которыми человечество расплачивается за удобства, обретенные с техническим прогрессом. Как уберечься пешеходу от встречи с...
2769. Применение закона Ома к цепям переменного тока 69 KB
  Применение закона Ома к цепям переменного тока Вариант лабораторной работы №324-дубль отличается от предыдущей иной формой представления результатов. По этой причине в описании отсутствует Введение – оно является общим для обоих вариантов....
2770. Мощность и коэффициент мощности в цепях переменного тока 287.5 KB
  Мощность и коэффициент мощности в цепях переменного тока Приборы и принадлежности: регулятор напряжения РНШ, проволочный реостат, магазин емкостей, катушка переменной индуктивности, амперметр, вольтметр, ваттметр. Введение. Пусть к клеммам источника...
2771. Вынужденные электрические колебания 114 KB
  Вынужденные электрические колебания Приборы и принадлежности: лабораторная панель Колебательный контур, генератор сигналов низкочастотный Г3-120, вольтметр В7-38, осциллограф С1-94. Введение. Рассмотрим электрическую цепь, состоящую из резистора с...
2772. Электронный осциллограф: устройство и применение 453 KB
  Электронный осциллограф. устройство и применение Приборы и принадлежности. осциллограф С1-1, понижающий трансформатор 220/127 В, реостат, вольтметр, миллиамперметр, магазин сопротивлений, лабораторная панель. Введение. Электронный осциллограф предна...
2773. Сложение электрических колебаний 374 KB
  Сложение электрических колебаний Приборы и принадлежности: лабораторная панель с генератором фиксированных частот, магазином сопротивлений Р-33 и реактивной нагрузкой, генератор Г3-120, фазометр Ф2-1, осциллограф С1-94. Осциллографический метод...
2774. Затухающие электрические колебания в колебательном контуре 181.5 KB
  Затухающие электрические колебания в колебательном контуре Приборы и принадлежности: лабораторная панель «Затухающие колебания», источник постоянного тока, осциллограф, магазин сопротивлений. Введение. Замкнутая электрическая цепь, состоящая ...
2775. Исследование и применение зеркального гальванометра 236 KB
  Исследование и применение зеркального гальванометра Приборы и принадлежности: гальванометр М17, лабораторная панель, длинный соленоид, катушка на вращающейся подставке. Введение. Гальванометр – это электроизмерительный прибор высокой чувствител...
2776. Измерение индукции магнитного поля электромагнита 57 KB
  Измерение индукции магнитного поля электромагнита Приборы и принадлежности: электромагнит, весы Ампера, разновес, два стабилизированных источника постоянного тока. Введение. Согласно закону Ампера на элемент тока  в магнитном поле действует сил...