Скінченні автомати В.Ковтунець Математична логіка і формальні системи

Означення скінченного автомата Скінченним автоматом називається система із шести обєктів M=(S,I,O,f,g,s 0 ), де S - множина станів I – вхідний алфавіт O – вихідний алфавіт f: S x I S - функція переходів g: S x I O - функція виходів s 0 - початковий стан

Пояснення до означення Автомат перебуває у стані s i, На вході автомату символ x. Якщо для цієї пари задано функції f та g, а саме f(s i,x)=s j, g(s i,x)=y, то автомат переходить у стан s i з виводом символа y O.

Описання скінченного автомата. Автоматні таблиці (таблиці станів) Станfg ВхідВихід 0101 S0S0 S1S1 S0S0 10 S1S1 S3S3 S0S0 11 S2S2 S1S1 S2S2 01 S3S3 S2S2 S1S1 00

Задання автомата з допомогою мультиграфа ( автомат з попередньої таблиці ) s0s0 s1s1 s3s3 s2s2 1,0 0,1 1,1 1,0 O,1 O,0 1,1 0,0 Start

Задання автомата на ланцюжках Вхідний ланцюжок = x 1 x 2 … x k. Обробка ланцюжка означає поетапне виконання переходів та виводів: s 1 = f(s 0, x 1 ) s 2 = f(s 1, x 2 ) …………. s k = f(s k-1, x k ). y 1 = g(s 0, x 1 ) y 2 = g(s 1, x 2 ) ……………… y k = g(s k-1, x k ).

Обробка ланцюжка На вході : x 1 x 2 … x k. На виході : y 1 y 2 … y k. Приклад. На вході автомата (слайд 4) На виході Вхід Станs0s0 s0s0 s1s1 s0s0 s1s1 s3s3 Вихід Новий станs0s0 s1s1 s0s0 s1s1 s3s3 s1s1

Автоматне відображення Означення. Автоматне відображення (автоматний оператор) – це оператор M, який діє на ланцюжки, і результатом кожного разу є вихідний лацюжок. Якщо на вході α = x 1 x 2 … x k, на виході ω = y 1 y 2 … y k, то M(α)= ω.

Властивості автоматного оператора Образ і прообраз мають однакову довжину Якщо α= α 1 α 2, і M(α 1 α 2 )= ω 1 ω 2, де довжини α 1 та ω 1 співпадають, то M(α 1 )= ω 1. Автоматні оператори – оператори без випередження.

Приклад 1. Автомат одиничної затримки s0s0 s1s1 s2s2 1,01,0 1,1 0,0 1,0 0,0 0,1 Start

Приклад 2. Автомат додавання двох чисел у двійковому форматі s0s0 s1s1 01,1 Start Вхідний алфавіт I={00,01,10,11} Вихідний алфавіт O={0,1} 00,0 10,1 01,0 00,1 11,1 10,0 11,0

Скінченні автомати без виходу Скінченним автоматом без виходу називається система із пяти обєктів M=(S,I,f,s 0,F), де S - множина станів I – вхідний алфавіт f: S x I S - функція переходів s 0 - початковий стан F S – множина заключних (приймаючих) станів.

Скінченні автомати без виходу Скінченні автомати без виходу призначені для задач розпізнавання. Задаються таблицям або діаграмами станів.

Скінченні автомати без виходу. Приклад 1. Станf Вхід 01 S0S0 S0S0 S1S1 S1S1 S0S0 S2S2 S2S2 S0S0 S0S0 S3S3 S2S2 S1S1

Скінченні автомати без виходу. Приклад 1. s0s0 s1s1 s3s3 s2s , 1 s0s0 S={s 0,s 1,s 2,s 3 }, I={0,1}, F={s 0, s 3 }

Скінченні автомати без виходу на ланцюжках. α = x 1 x 2 … x k. s 1 = f(s 0, x 1 ) s 2 = f(s 1, x 2 ) …………. s k = f(s k-1, x k ).

Скінченні автомати без виходу на ланцюжках. Означення 2. Скінченний автомат допускає (приймає) ланцюжок α, якщо він переводить початковий стан s 0 в заключний стан s k, s k F. Означення 3. Скінченний автомат розпізнає мову L, якщо всі ланцюжки цієї мови доускаються автоматом. Означення 3. Два скінченні автомати називаються еквівалентними, якщо вони розпізнають одну й ту саму мову L.

Приклад ропізнавання мови автоматом M s0s0 s1s1 s3s3 s2s , 1 L(M)={1,01}

Недетерміновані скінченні автомати Недетермінованим скінченним автоматом без виходу називається система M=(S,I,f,s 0,F), де S - множина станів I – вхідний алфавіт f: S x I P (S) (множина всіх підмножин множини S) - функція переходів s 0 - початковий стан F S – множина заключних (приймаючих) станів.

Теорема. Якщо мову розпізнає недетермінований автомат, то її розпізнає і детермінований автомат.