Приклад недетермінованого скінченного автомата

Побудуємо автомат в алфавіті , який буде розпізнавати слова, в яких є хоча б одна двійка.

Наприклад, w₁ = 12231 L(M), w₂ = 1131131 L(M).

Визначимо стани:

- початковий стан: двійки ще не було

- заключний стан: двійка вже була.

Отже, автомат має вигляд .

Визначимо функцію переходів

Функцію прийнято зображати у вигляді таблиці переходів:

Cтани	Вхідні символи
	1	2	3

Функцію можна зобразити у вигляді діаграми переходів:

Рис.7.

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

Нехай у нас є ланцюжок 12231. Випишемо всі можливі послідовності конфігурацій:

Оскільки серед останніх конфігурацій присутня заключна конфігурація , то існує послідовність, що перетворює початкову конфігурацію в заключну. Це означає, що ланцюжок

Приклад детермінованого скінченного автомата

Знов побудуємо автомат в алфавіті , який буде розпізнавати слова, в яких є хоча б одна двійка. Але тепер він буде детермінованим.

Визначимо такі ж стани, як і раніше, але змінимо функцію переходів

Cтани	Вхідні символи
	1	2	3

Рис.8.

Отже, автомат має вигляд . Він повністю визначений і мінімальний.

Оскільки автомат детермінований, то для будь-якого ланцюжка існує єдина послідовність конфігурацій. Нехай у нас є ланцюжок 12231. Тоді послідовність конфігурацій має вигляд:

Ця послідовність перетворює початкову конфігурацію в заключну. Це означає, що ланцюжок

Зазначимо, що працювати з детермінованим автоматом простіше, ніж з недермінованим, але, як правило, для складних мов його непросто визначити. Існують алгоритми перетворення недетермінованого автомата в детермінований, а потім ­­– і у мінімальний. Вони розглянуті далі, а нижче наведено програму, яка моделює роботу створеного користувачем детермінованого скінченного автомата для введеного рядка символів.

Моделювання роботи скінченного детермінованого автомату

Алгоритм перевірки належності ланцюжка мові автомата можна реалізувати так:

q = q0; // початковий стан автомата

symbol = GetChar(); // зчитування першого символу

// з вхідної стрічки

while (symbol != eos) // поки не кінець стрічки

{

// перехід автомату в інший стан по прочитаному символу

q = Delta(q, symbol); // функція переходів Delta керує

// роботою автомата

symbol = GetChar(); // зчитування наступного символу з

// вхідної стрічки

} // стрічку прочитано

If (q is in f) // автомат попав в заключний стан ?

return "Yes"; // ланцюжок належить мові автомата

else return "No"; // ланцюжок не належить мові автомата

Застосуємо алгоритм для детермінованого скінченного автомата, який будується на динамічній HTML-сторінці.

Сторимо проект DHTML.

Нехай користувачу пропонується ввести алфавіт , множину станів Q і множину заключних станів F детермінованого скінченого автомата. По натисканню командної кнопки Avtomat побудуємо таблицю переходів для вводу ДСА (елемент керування Avt).

Private Function cmdAvt_onclick() As Boolean

Dim i As Integer, s As String

s = " "

’формування рядка з назвами вхідних символів

For i = 1 To Len(txtAlf.Value)

s = s + Mid(txtAlf.Value, i, 1) + " "

Next

’Формування стовпця з назвами станів

For i = 1 To Len(txtStan.Value)

s = s + Chr(13) + Mid(txtStan.Value, i, 1)

Next

Avt.Value = s

End Function

Після вводу ДСА і ланцюжка символів (Word) по натисканню командної кнопки Check визначимо, чи належить введене користувачем слово мові автомата.

Private Function cmdCheck_onclick() As Boolean

Dim Delta(0 To 10, 0 To 10) As String, i, k, j As Integer

Dim s, stan, symbol As String

s = Avt.Value

’ заповнення матриці переходів Delta данними користуваяа

k = 1: i = 1

While InStr(k, s, Chr(13)) <> 0

k = InStr(k, s, Chr(13)) + 2

For j = 1 To Len(txtAlf.Value)

Delta(i, j) = Mid(s, k + 2 * j, 1)

Next

i = i + 1

Wend

’ моделювання роботи ДСА для введеного слова Word

stan = Mid(txtStan.Value, 1, 1)

For i = 1 To Len(txtWord.Value)

symbol = Mid(txtWord.Value, i, 1)

stan = Delta(InStr(txtStan.Value, stan), _

InStr(txtAlf.Value,symbol))

Next

If stan = "" Then

txtRez.Value = "No"

Else

’автомат попав в заключний стан ?

If InStr(txtZakl, stan) Then txtRez.Value = "Yes" Else _ txtRez.Value = "No"

End If

End Function