Кінцеві автомати

Основні області застосування:

1. Програмне забезпечення для проектування і побудови моделі поведінки цифрових пристроїв.

2. Лексичний аналіз під час проектування побудови компіляторів для мов програмування і під час аналізу текстів природними мовами.

2. Програмне забезпечення для опрацювання і пошуку інформації на web-сторінках.

4. Програмне забезпечення для верифікації систем, котрі мають кінцеве число різноманітних станів (комунікація, криптографія і т.д.).

Автомат Мілі – це впорядкована п’ятірка {Q, X, Y, f(q), g(q)}, де Q – множина станів автомату, X – алфавіт вхідних символів, Y – алфавіт вихідних символів, f(q) – функція переходу (Q cross X=Q), q(p) – функція виходу (Q cross X = Y).

Класифікація автоматів:

1. якщо з множини станів автомату можна виділити деякий стан q(0), який називається початковим, то автомат називається ініціальним (впорядкована п’ятірка);

2. у залежності від визначення множини станів, алфавітів вхідних та вихідних символів автомату розрізняють:

- кінцевий автомат (якщо три множини Q, X, Y кінцеві);

- некінцевий (якщо хоча б одна з них некінцева).

3. у залежності від визначення функцій переходу розрізняють:

- повний автомат (якщо функції переходів і виходу повністю визначені);

- частковий автомат (якщо одна з функцій переходу чи виходу визначена лише частково);

4. у залежності від правил визначення функцій переходу розрізняють:

- детермінований автомат (якщо f(q) – функція, тобто існує однозначний перехід із стану q(i) в q(j) під час зчитування символу з алфавіту X);

- недетермінований (- відношення, тобто, існує декілька варіантів переходів з стану q(i));

5. якщо автомат представлений впорядкованою четвіркою {Q, X, f(q), F} чи, для ініціального автомату, впорядкованою п’ятіркою {Q, X, f(q), q(0), F}, F – підмножина станів Q, що називається заключними (акцентовними), то такий автомат – автомат без виходу (акцептор, Х-автомат);

6. Автомат Мура – частковий випадок автомату Мілі, у якого функція виходів g(q) виражається через функцію переходів f(q) наступним виразом: q(q)= h(f(q)), де h - це A->Y.

Способи представлення кінцевих автоматів:

1) Таблиці переходів і виходів автомату

Це дві матриці однакової розмірності, де рядки позначені символами з вхідної множини, а стовпчики – станами. //Q={0,1,2,3}, X={a,b}, Y={+,-}, q(0)=0; (f 0 1 2 3)/(a b)// Бажано, будуючи такі таблиці, стани розставляти по порядку – спочатку початковий, а в кінці, якщо є наявним, - кінцевий.

2) Граф переходів і виходів автомату

Це орієнтований граф, вершини якого визначають стани автомату, а ребра – взаємозв’язки (пара символів, розділених /, де перший – символ вхідного алфавіту, другий - вихідного). Умови його автоматності:

- умова однозначності (не існує двох ребер з однаковими вхідними відмітками, які виходять з одної і тої ж вершини);

- умова повноти (для довільних вершин і вхідного символу існує ребро, що виходить з цієї вершини і позначене цим символом).

//є кінцевий стан – кружечком обвели, а початковий стрілкою вказують.

Стан q(i) – досяжне з стану q(0), якщо існує вхідне слово p, яке переводить автомат з стану q(0) y q(i). Для встановлення досяжності достатньо визначити чи існеє шлях з вершини q(0) y q(i) у графі переходів і виходів.

Кооооооооооооооооооооооооооооооооооооооооооооод

ддддддддддддддд

Поиск по сайту: