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

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


 

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

72730. Создание простейшего прикладного приложения: калькулятор, просмоторщик рисунков, графический редактор, текстовый редактор, медиаплеер 4.9 MB
  Цель работы. Разработка приложений использующих главное меню формы всплывающего меню строки состояния панели инструментов быстрых кнопок с картинками подсказок к кнопкам а также стандартных диалогов открытия и сохранения файлов на примере создания приложения для просмотра графических файлов точечных рисунков.
72732. Изучение компонентов среды С++ Builder 6: TStringGrid (таблица строк), TMainMenu. Работа с массивами данных 264 KB
  Получение навыков работы с компонентами TStringGrid (таблица строк), TMainMenu (главное меню), программирования ввода матрицы смежности графа с помощью компоненты TStringGrid, разработки классов для решения задач на графах.
72733. История одного ордена (орден Отечественной войны) 75.5 KB
  Цель: Через знакомство с историей ордена Отечественной войны установить имена ветеранов Великой Отечественной войны проживающих в нашем поселке награжденных этим орденом. Актуальность: В 2011 году 22 июня весь наш народ вспоминал одну из самых трагичных страниц в истории России начало Великой Отечественной...
72734. История семьи в судьбе Отечества (вечер воспоминаний) 35 KB
  Цель: Затронуть патриотические чувства учащихся, сделать акцент на выборе доблестной и почетной профессии военного. Побуждать родителей делиться опытом о том, как в семье хранит память о старшем поколении, воспитываются моральные ценности, строятся отношения между поколениями, формируется отношение к окружающему миру.
72735. Бактерии полезные и вредные 42 KB
  Цель: выяснить какие бактерии полезные а какие вредные. Задачи исследования: выяснить где живут бактерии от чего зависит их жизнь какие бывают бактерии и микробы. Сидя перед телевизором часто слышу слова бактерии полезные бактерии вредные бактерии пробиотики пребиотики высказывания о различных йогуртах...
72736. Исследование влияния состава воздуха на здоровье населения города Омска 138.5 KB
  Город Омск – один из крупнейших городов азиатской части России с населением более 1,1 млн. человек. В процессе своей жизнедеятельности город, как и любой другой крупный населенный пункт, производит значительное количество веществ, загрязняющих окружающую среду: воздух, водные объекты и территорию.