Лабораторна робота № 2.
Теорія автоматів.
Скінчений автомат без виходів: A = <A, S, s0, F, f>, де А = {a, b, c, …} – вхідний алфавіт, S = {0, 1, 2, …} – множина станів, s0∈S – початковий стан, F⊆S – множина фінальних (заключних) станів, f: S×A→S – функція переходів (автомат, знаходячись у певному стані та читаючи черговий символ зі вхідного слова переходить в інший стан згідно цієї функції доти, поки не закінчилось слово та поки існують відповідні переходи).
Функція переходів є не всюди визначеною та може бути багатозначною (у випадку недетермінованого автомату).
Слово e – слово нульової довжини. Таким чином, для будь-якого символу або слова w справедливо: we=ew=w. Якщо автомат допускає e-переходи, то використовується функція переходів вигляду S×(A∪{e})→S замість звичайної для задання такого автомату.
Автомат A сприймає (допускає, розпізнає) слово w, якщо, читаючи по одному символу з цього слова (за кожен такт роботи – зліва направо) і виконуючи переходи відповідно до функції переходів f, починаючи з стану s0, він потрапляє через |w| кроків у стан f∈F.
|w| = довжина слова w,
||Set|| = потужність множини Set.
Автомат A на вході програми (та на виході, де потрібно) подається у вигляді текстового файлу наступної структури:
||A||
||S||
s0
||F|| f1∈F … f||F||∈F // перелічені через проміжок кількість та всі стани з множини F
s a s’ // всі такі трійки, що (s, a, s’) ∈ f, через проміжок, по одній на рядок – до кінця файлу.
Розробити та реалізувати представлення скінченого автомата в пам`яті ЕОМ.
19****. Виявити, чи є еквівалентними два задані детерміновані скінчені автомати, що допускають e-переходи.