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}.

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


 

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

52734. Робота з обдарованими дітьми в умовах сільської малокомплектної школи 171.5 KB
  Науково обґрунтований підхід до процесу побудови педагогічної технології виховання інтересу в учнів до занять фізичною культурою та спортом дає змогу вчителям фізичної культури тренерам класним керівникам шкільним психологам батькам всебічно зрозуміти суть і причини явищ і процесів у розвитку масового охоплення школярів оздоровчою і фізкультурноспортивною діяльністю через самостійні заняття відвідування спортивних секцій груп ЗФП участі в спортивних змаганнях. У період навчання у школі в учнів розкриваються творчі здібності та...
52735. ІНТЕГРОВАНІ ЗАНЯТТЯ У КОНТЕКСТІ ПРОЕКТНОЇ ТЕХНОЛОГІЇ 1.22 MB
  Існують три рівні інтеграції змісту навчального матеріалу: Отже одним із шляхів підвищення якості освіти є впровадження у практику викладання бінарних та інтегрованих занять особливо з дисципліни Іноземна мова за професійним спрямування які є складовою нормативної частини типових навчальних планів підготовки молодших спеціалістів у вищих навчальних закладах І ІІ рівнів акредитації усіх спеціальностей і можлива інтеграція англійської мови із дисциплінами професійноорієнтованого спрямування. Але такий шлях використання міждисциплінарних...
52736. Формування соціальної активності підлітків через використання виховного педагогічного потенціалу спадщини В.Сухомлинського 103.5 KB
  Сухомлинський А яким бути саме мені Ким бути Як жити Як бути корисним людям Які якості треба виховувати в собі сьогодні щоб комфортно почуватися в житті завтра Якою має бути особистість XXI сторіччя Ці питання соціалізації й самореалізації особистості є найактуальнішими питаннями сьогодення. Соціальну активність особистості ще можна визначити як якість її звязків із суспільством. Від соціальної активності особистості залежить як правило і її соціальна мобільність. Під його керівництвом у Павлиській школі було...
52737. Створення ситуації успіху в навчальній діяльності школярів 378.5 KB
  Створення ситуації успіху в навчальній діяльності школярів це проблема до якої все частіше звертається сучасна педагогічна наука. Провівши огляд та аналіз літератури з теми Створення ситуації успіху на уроках стверджую що обрана тема є актуальною для освіти залишається лише допомогти дитині в період формування її особистості ні в якому разі не позбавляти школяра чекання завтрашньої радості віри у свої можливості...
52738. Формування творчої особистості молодшого школяра через використання інтерактивних технологій на уроках читання у початкових класах 69.5 KB
  В теорії і практиці навчання особливо гостро стоїть питання про розвиток творчих здібностей учнів. Під час такого діалогу важливо навчити кожну дитину розмірковувати гнучко підходити до розвязання проблем знаходити нові оригінальні рішення для того щоб відчути задоволення від навчання. Зацікавленість є ефективним засобом успішного навчання необхідною умовою досягнення позитивних наслідків. Ефективне навчання неможливе без активізації пізнавальної діяльності розвитку творчих здібностей.
52739. Формування комунікативно-мовленнєвих умінь і навичок молодших школярів на уроках читання 165 KB
  Розвиток мовленнєвокомунікативних умінь та навичок учнів на нетрадиційних уроках читання. Формування звязного мовлення та навичок міжособистісного спілкування у процесі роботи з художнім текстом Уроки читання має великі можливості для реалізації мети розвитку комунікативної культури дітей. На уроках читання та позакласного читання учні вчаться усвідомлювати фактичний зміст твору переказувати прочитане виділяти основних персонажів обговорювати оповідання та стисло висловлювати своє ставлення до нього.
52740. Компетентностный подход к формированию личности средствами проектных технологий 470.5 KB
  Использование проектного метода делает студента самостоятельным приспособленным к жизни умеющим ориентироваться в разнообразных ситуациях способствует развитию познавательных творческих навыков умений самостоятельно конструировать свои знания умений ориентироваться в информационном пространстве; развитию критического мышления навыков информационной деятельности. Концепция компетенции выходит за рамки квалификации и представляет компетенцию как комбинацию знаний умений навыков и отношений соответствующих определенному содержанию...
52741. Диференційоване навчання в початковій школі 89.5 KB
  Працюючи в школі я впевнилась що особистіснорозвивальна спрямованість освіти реалізація якої є головним завданням сучасної школи неможлива без диференційованого навчання. Головне завдання вчителів початкової ланки не забути жодної дитини дати можливість розкрити все краще закладене природою сімєю школою. Враховуючи те що рівень готовності учнів до навчальної діяльності різний необхідно конструювати диференційовані завдання для школярів з різними навчальними можливостями. Такі завдання мають поєднувати навчальний процес усього...
52742. Формування предметно-культурологічних компетентностей учнів через моделювання культурно-освітнього середовища 139 KB
  предметнокультурологічних компетентностей учнів має особливу практичну значущість та дозволяє досягти нової якості освіти. Основна ідея досвіду її інноваційна значущість Формування компетентної особистості учня в процесі вивчення літератури здійснюється через моделювання культурноосвітнього середовища як дидактичної одиниці інноваційного освітнього процесу на засадах поєднання дІяльнісного особистісноорієнтованого компетентнісного підходів шляхом забезпечення міжпредметної інтеграції використання розвиваючих інтерактивних технологій...