Page 10 - 4625

M = < Q, Σ, δ, q , F >,
0
де Q = {q , q , . . , q n−1 } – скінченна множина станів
1
0
автомата;
- Σ = {a , a , .. , a 1m } – скінченна множина вхідних симво-
1
2
лів (вхідний алфавіт);
- q ∈ Q – початковий стан автомата;
0
- δ – відображення множини Q*Σ в множину P (Q).
Відображення δ, як правило називають функцією переходів;
- F  Q – множина заключних станів. Елементи з F
називають заключними або фінальними станами.
Якщо М – скінченний автомат, то пара (q, w) ∈ Q Σ*
∗
називається конфігурацією автомата М. Оскільки скінчений
автомат – це дискретний пристрій. Такт скінченого автомата
М задається бінарним відношенням ⊨, яке визначається на
конфігураціях:
(q , aw) ⊨ (q , w), якщо δ (q , a) містить q та для всіх w ∈ Σ*.
2
2
1
1
Означення. Скінченний автомат М розпізнає (допускає)
ланцюжок w, якщо
(q , w) ⊨* (q, ε) для деякого q ∈ F,
0
де ⊨* - рефлексивно-транзитне замикання бінарного відно-
шення ⊨.
Означення. Мова, яку допускає автомат М (розпізнає
автомат М)
L (M) = {w | w ∈* та (q , w) ⊨* (q, ε), q ∈ F}.
0
На практиці, при визначенні скінченного автомата М, ви-
користовують декілька способів визначення функції δ, наприк-
лад:
- це табличне визначення δ;
- діаграма проходів скінченного автомата.
Табличне визначення функції δ – це таблиця M (q , a ), де
i
j
a ∈ Σ, q ∈ Q, тобто
j
i
M (q , a ) = {q |, q ∈ δ(q , a )}.

i
j

i
j
Діаграма переходів скінченного автомата М – це невпо-
рядкований граф G (V, P), де V – множина вершини графа, а P
– множина орієнтованих дуг, причому з вершини q у вершину
i
9