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

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


 

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

20732. Группа аффинных преобразований и ее подгруппы. Приложения аффинных преобразований к решению задач 105 KB
  Зададим на плоскости два аффинных репера аф.репером R на плоскости наз. Упорядоченная тройка точек ОA1A2 этой плоскости не лежащих на одной прямой. Пишут:R={ОA1A2} R={O1 2 } R={O 1 2} и рассмотрим отображение f плоскости в себя по закону: координаты точки M=fM в репере R равны соответствующим координатам х у точки М в репере R.
20733. Группа преобразований подобия и ее подгруппы. Приложение преобразований к решению задач 95.5 KB
  Группа преобразований подобия и ее подгруппы. Гомотетия с коэффициентом также является частным случаем подобия . Как и для движения можно доказать теорему которая делает определение подобия конструктивным: Как и для движений можно показать что и Из этих формул следует что всякое подобие можно представить в виде произведения гомотетии и движения . Теорема: множество преобразований подобия на плоскости образуют группу.
20734. Проективная плоскость и ее модели. Группа проективных преобразований. Приложение к решению задач 29 KB
  Дополним прямую точкой бесконечно удаленной которую будем считать точкой соответствующей прямой х параллельной прямой а. Прямая дополненная бесконечно удаленной точкой называется проективной прямой. Плоскость дополненная бесконечно удаленной прямой называется проективной плоскостью. Пространство дополненное бесконечно удаленной плоскостью называется проективным пространством.
20735. Группа движений. Классификация 115.5 KB
  Классификация Движение такое преобразование плоскости которое сохраняет расстояние между любыми двумя точками. Это определение отличается от определений поворота симметрии и переноса тем что не является конструктивным нельзя определить как выполнять движение. Теорема: каковы бы ни были два прямоугольных декартовых репера и существует движение переводящее так что ориентация сохраняется. Если оба репера ориентированы одинаково то движение не изменяет ориентацию фигур иначе меняет на противоположную.
20736. Трехмерное евклидово пространство. Скалярное, векторное и смешанное произведение векторов. Приложение к решению задач 55.5 KB
  Скалярное векторное и смешанное произведение векторов. Основные отношения сумма векторов скалярное произведение умножение вектора на число. Аксиомы: аксиомы линейных векторов аксиома размерности аксиомы скалярного произведения. Линейное векторное пространство называется евклидовым если каждым двум векторам a и b этого пространства поставлено в соответствие число α называемое скалярным произведением этих векторов.
20737. Система аксиом Вейля трехмерного евклидова пространства и ее непротиворечивость 101 KB
  Геометрия Вопрос №11 Система аксиом Вейля трехмерного евклидова пространства и ее непротиворечивость Пусть трехмерное векторное пространство на полем вещественных чисел а непустое множество элементы которого называются точками. Предполагается также что дано множество отображений каждое из которых является отображением вида . Множество называется трехмерным вещественным евклидовым пространством если выполнены следующие аксиомы. Множество является множеством положительноопределенных билинейных форм таких что если то где .
20738. Линейные отображения (операторы). Матрица линейного оператора. Собственные векторы и собственные значения. Характеристическое уравнение 147 KB
  Матрица линейного оператора. Ядром линейного оператора называется Образом линейного оператора называется Ядро Образ Теорема. Каждый вектор разложим по базису B: Столбцы матрицы линейного оператора представляют собой координатные столбцы образов базисных векторов относительно данного базиса.АBfматрица линейного оператора.
20739. Ранг матрицы 107.5 KB
  Вопрос №11 Ранг матрицы. Столбцевым рангом матрицы называют ранг системы столбцов. Строчечным рангом матрицы называют равный столбцевому для произвольной матрицы. Согласно теореме можно говорить просто о ранге матрицы не уточняя о ранге системы строк или столбцов идет речь.