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

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


 

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

3115. Разработка и исследование двухконтурной структуры подчиненного регулирования скорости электропривода постоянного тока 386 KB
  Очень трудно представить себе современную жизнь человека без систем автоматического управления (САУ). Методы автоматического управления широко используются в производстве и научных исследованиях. Одной из главных задач автоматики является...
3116. ИССЛЕДОВАНИЕ ТЕПЛОЗАЩИТНЫХ КАЧЕСТВ МНОГОСЛОЙНОЙ СТЕНОВОЙ ОГРАЖДАЮЩЕЙ КОНСТРУКЦИИ 111 KB
  Лабораторная работа №1 ИССЛЕДОВАНИЕ ТЕПЛОЗАЩИТНЫХ КАЧЕСТВ МНОГОСЛОЙНОЙ СТЕНОВОЙ ОГРАЖДАЮЩЕЙ КОНСТРУКЦИИ Цель работы: знакомство с экспериментальными методами исследования теплозащитных качеств ограждения и принципам анализа основных параметров, хара...
3117. ИССЛЕДОВАНИЕ ТЕПЛОЗАЩИТНЫХ КАЧЕСТВ ОКОННЫХ ОГРАЖДЕНИЙ 99.5 KB
  ИССЛЕДОВАНИЕ ТЕПЛОЗАЩИТНЫХ КАЧЕСТВ ОКОННЫХ ОГРАЖДЕНИЙ Цель работы: знакомство с экспериментальными методами исследования теплозащитных качеств оконных заполнений. Приборы и оборудование: фрагмент светопрозрачного оконного ограждения, комплект смонти...
3118. Алгоритм диагностики трансмиссии автомобиля Daewoo Matiz 243.29 KB
  Daewoo Matiz — микролитражный городской автомобиль класса «А». Разработан и выпускается южнокорейским подразделением General Motors (Daewoo), а также другими автозаводами по лицензии.
3119. Управление затратами транспортного цеха ОАО Омскавтотранс 1.03 MB
  На рынке автотранспортных услуг в новых рыночных условиях управление затратным механизмом перевозок, а значит и повышение их эффективности, является жизненно важной задачей любого автотранспортного предприятия. Одна из наиболее актуальных п...
3120. Множества и операции над ними 133 KB
  Множества и операции над ними Написать программу, в которой для конечных упорядоченных множеств реализовать все основные операции с помощью алгоритма типа слияния. Допустима организация множеств в виде списка или в виде массива...
3121. Написание программы реализующей параллельную работу нескольких процессов 121.5 KB
  Необходимо написать программу, реализующую параллельную работу нескольких процессов. Каждый процесс может состоять из одного или нескольких потоков. Любой из потоков, работающих в составе этих процессов, может быть приостановлен и вновь запущен неко...
3122. Реализация параллельной работы нескольких процессов программным методом 258 KB
  При написании программы выяснилось, что имеющиеся в Borland Pascal функции вывода (Write[Ln]) не подходят, т. к. в том случае, когда несколько процессов выводят информацию на экран может случиться
3123. Платежные карты: Бизнес-энциклопедия 115.64 MB
  Платежные карты: Бизнес-энциклопедия Важнейшая социально-политическая задача, которую решает сегодня банковская система России, —повышение доступности финансовых услуг для граждан страны. Банковская активность, связанная с...