knu/csc/appl-math/c3s2/sys-prog

Скінченні автомати та алгоритми з ними

Скінчений автомат без виходів: $\mathcal{A} = \left\langle A, S, s_0, F, f\right\rangle$ , де

$A = \{a, b, c, \ldots\}$ — вхідний алфавіт;
$S = \{0, 1, 2, \ldots\}$ — множина станів;
$s_0 \in S$ — початковий стан;
$F \subseteq S$ — множина фінальних (заключних) станів;
$f: S \times A \to S$ — функція переходів (автомат, знаходячись у певному стані та читаючи черговий символ зі вхідного слова переходить в інший стан згідно цієї функції доти, поки не закінчилось слово та поки існують відповідні переходи).

Функція переходів є не всюди визначеною та може бути багатозначною (у випадку недетермінованого автомату).

Слово $\varepsilon$ — слово нульової довжини. Таким чином, для будь-якого символу або слова $w$ справедливо: $w \varepsilon = \varepsilon w = w$ . Якщо автомат допускає $\varepsilon$ -переходи, то використовується функція переходів вигляду $S \times (A \cup \{\varepsilon\}) \to S$ замість звичайної для задання такого автомату.

Автомат $\mathcal{A}$ сприймає (допускає, розпізнає) слово $w$ , якщо, читаючи по одному символу з цього слова (за кожен такт роботи — зліва направо) і виконуючи переходи відповідно до функції переходів $f$ , починаючи з стану $s_0$ , він потрапляє через $$

$кроків у стан$ \mathcal{f} \in F$$.

Останні кілька позначень:

$\mid w\mid$ — довжина слова $w$ ;
$\|M\|$ — потужність множини $M$ .

Автомат $\mathcal{A}$ на вході програми (та на виході, де потрібно) подається у вигляді текстового файлу наступної структури:

$\|A\|$ ;
$\|S\|$ ;
$s_0$ ;
$\|F\|$ , $f_1 \in F, \ldots, f_{\|F\|} \in F$ — перелічені через проміжок кількість та всі стани з множини $F$ ;
$s, a, s'$ — всі такі трійки, що $(s, a, s') \in f$ , через проміжок, по одній на рядок — до кінця файлу.

Розробити та реалізувати представлення скінченного автомата в пам’яті ЕОМ.

Варіанти

Встановити, які літери вхідного алфавіту не сприймає скінченний детермінований автомат.
Виявити недосяжні та тупикові стани скінченного автомату.
Розробіть алгоритм та реалізуйте програму, що моделює роботу недетермінованого скінченного автомата.
Розробити та реалізувати алгоритм перевірки: чи допускає скінченний автомат слова виду $w = w_0 w_1$ , де $w_0$ — наперед задане (фіксоване) слово, а $w_1$ — деяке слово, таке що $w$ допускається скінченним автоматом. На вхід алгоритму подавати $w_0$ .
Розробити та реалізувати алгоритм перевірки: чи допускає скінченний автомат слова виду $w = w_1 w_0$ , де $w_0$ — наперед задане (фіксоване) слово, а $w_1$ — деяке слово, таке що $w$ допускається скінченним автоматом. На вхід алгоритму подавати $w_0$ .
Розробити та реалізувати алгоритм перевірки: чи допускає скінченний автомат слова виду $w = w_1 w_0 w_2$ , де $w_1$ та $w_2$ — наперед задані (фіксовані) слова, а $w_0$ — деяке слово, таке що $w$ допускається скінченним автоматом. На вхід алгоритму подавати $w_1$ та $w_2$ .
Розробити та реалізувати алгоритм перевірки: чи допускає скінченний автомат слова виду $w = w_1 w_0 w_2$ , де $w_0$ — наперед задане (фіксоване) слово, а $w_1$ та $w_2$ — деякі слова, такі що $w$ допускається скінченним автоматом. На вхід алгоритму подавати $w_0$ .
$^\star$ Знайти всі слова (без періодичних фрагментів), що сприймаються заданим скінченним автоматом.
$^\star$ Виявити, чи допускає скінченний автомат всі можливі (виходячи з алфівіту) слова заданої довжини $k$ .
$^{\star\star}$ Реалізувати алгоритм пошуку слова мінімальної довжини, що допускається двома скінченними автоматами.
$^{\star\star}$ Реалізувати алгоритм мінімізації детермінованого скінченного автомата.
$^{\star\star}$ Реалізувати алгоритм перетворення недетермінованого скінченного автомата (без $\varepsilon$ -переходів) в еквівалентний йому детермінований скінченний автомат.
$^{\star\star}$ Виявити, чи є еквівалентними два задані детерміновані скінченні автомати.
$^{\star\star\star}$ Виявити, чи допускає скінченний автомат слова довільної довжини.
$^{\star\star\star}$ Виявити, чи допускає скінченний автомат слова довільної непарної довжини.
$^{\star\star\star}$ Виявити, чи допускає скінченний автомат слова довільної, але виключно парної довжини.
$^{\star\star\star\star}$ Виявити, чи є еквівалентними два задані недетерміновані скінченні автомати.
$^{\star\star\star\star}$ Побудувати регулярний вираз, що задає мову, яка розпізнається скінченним автоматом (мову слів, що ним сприймаються).
$^{\star\star\star\star}$ Виявити, чи є еквівалентними два задані детерміновані скінченні автомати, що допускають $\varepsilon$ -переходи.

Назад до усіх лаб

Назад на головну