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

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


 

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

28084. Информационное обеспечение охраны ос и пп 6.8 KB
  Информационное обеспечение охраны окружающей среды это сбор переработка хранение и обязательно подготовка к использованию информации которая необходима для оценки состоянии собственно окружающей среды экологической деятельности и принятия различного рода решений в этой области. Информационное обеспечение охраны окружающей среды включает в себя: необходимую информацию как объект обеспечения; процессы работы с информацией завершающиеся ее подготовкой к использованию; распределение или предоставление информации...
28085. Классификация источников экологического права 10.52 KB
  По юридической силе все источники подразделяются на законы и подзаконные акты. Законы как источники экологического права представляют собой нормативные акты принимаемые представительным и законодательным органом РФ Федеральным Собранием состоящим из двух палат Совета Федерации и Государственной Думы. Подзаконные нормативные акты как источники экологического права представляют собой документы правового характера принимаемые Правительством РФ правительствами республик РФ органами исполнительной...
28086. Конституционные основы охраны окружающей среды 4.7 KB
  Законы и иные НПА не должны противоречить конституции РФ. Наиболее важные положения по вопросам использования и охраны окружающей природной среды предусмотрены в нормах Конституции РФ. Провозглашение осуществление и защита предусмотренных в Конституции экологических прав физических и юридических лиц по поводу окружающей среды является одним из направлений развития конституционного права России. Нормы Конституции РФ можно разбить на две группы: первая непосредственно посвященная...
28087. Международное экологическое право 3.31 KB
  Международное экологическое право МЭП или международное право окружающей среды составная часть отрасль системы международного права представляющая собой совокупность норм и принципов международного права регулирующих деятельность его субъектов по предотвращению и устранению ущерба окружающей среде из различных источников а также по рациональному использованию природных ресурсов. Объектом МЭП являются отношения субъектов международного права по поводу защиты и разумной эксплуатации окружающей среды на благо нынешнего и будущих...
28088. Общественные экологические организации и их роль в обеспечении экологической безопасности 2.77 KB
  Важно чтобы научнотехнический потенциал общественных объединений нашел достойное применение и поддержку в решении многих проблем по оздоровлению окружающей среды улучшению здоровья населения рациональному использованию природных ресурсов. Общественные и иные некоммерческие объединения осуществляющие деятельность в области охраны окружающей среды имеют право: разрабатывать пропагандировать и реализовывать в установленном порядке программы в области охраны окружающей среды защищать права и законные интересы граждан в области охраны...
28089. Органы муниципального управления в области ПП и охраны ОС. Их функции. На примере Омской области 9.19 KB
  10 Федерального закона Об охране окружающей среды управление в области охраны окружающей среды осуществляется органами местного самоуправления в соответствии с настоящим Федеральным законом другими федеральными законами и иными нормативными правовыми актами Российской Федерации законами и иными нормативными правовыми актами субъектов Российской Федерации уставами муниципальных образований и нормативными правовыми актами органов местного самоуправления. 132 Конституции РФ органы местного самоуправления самостоятельно управляют муниципальной...
28090. Сформулюйте вимоги для приведеної в завданні функції інформаційної системи 132.55 KB
  Запустити сервер Відключити сервер під ними розташовуються інтерфейсні елементи для управління параметрами компоненту на формі серверу. Провести тестування роботи серверу під управлінням контролера. Умова завдання: Компонент на формі серверу Функції контролера автоматизації управління компонентом на формі серверу TListBox При натисненні: 1ї кнопки в список TListBox на сервері додається рядок з поля редагування TEdit; 2ї кнопки із списку видаляється поточний рядок; 3ї кнопки список очищуеться.
28091. Виконайте декомпозицію інформаційної системи по її опису 148.64 KB
  У телефонній компанії ведеться оперативний облік міжміських розмов з реквізитів: номер телефону прізвище імя побатькові абонента ідентифікаційний код стать дата народження вік адреса час початку та закінчення розмови її тривалість населений пункт та номер телефону з яким велась розмова тариф в залежності від пункту усередині чи поза однієї області і періоду доби день чи ніч вартість розмови відомості про сплату послуг з зазначенням дат та сум. Розробити БД та підготувати звіт про стан оплати розмов за вибраний квартал за...