Призначення: перетворення вхідного тексту програми з формату зовнішнього представлення в машинноорієнтований формат – послідовність лексем.
Лексема – це ланцюжок літер елементарний об’єкт програми, що несе певний семантичний зміст. В подальшому кожну лексему будемо представляти як пару
(<клас_лексеми, ім’я_лексеми>)
В більшості мов програмування для визначення класів лексем достатньо скінчених автоматів.
Скінчені автомати
Означення: Недетермінований скінчений автомат – це п’ятірка
М = < Q, S, d, q0, F>, де
- Q = {q0, q1,.., qn-1} – скінчена множина станів автомата;
- S = {a1, a2,.., am} – скінчена множина вхідних символів (вхідний алфавіт);
- q0 Î Q – початковий стан автомата;
- d – відображення множини Q*S в множину P (Q). Відображення d як правило називають функцією переходів;
- F Í Q – множина заключних станів. Елементи з F називають заключними або фінальними станами.
Якщо М – скінчений автомат, то пара (q, w) Î Q*S* називається конфігурацією автомата М. Оскільки скінчений автомат – це дискретний пристрій, він працює по тактам. Такт скінченого автомата М задається бінарним відношенням |=, яке визначається на конфігураціях:
(q1,aw) |= (q2,w), якщо d(q1, a) містить q2 та для всіх w Î S*.
Означення. Скінчений автомат М розпізнає (допускає) ланцюжок w, якщо
(q0, w) |=* (q, e) для деякого q Î F, де
|=* - рефлексивно-транзитивне замикання бінарного відношення |=.
Означення. Мова, яку допускає автомат М (розпізнає автомат М)
L(M)={ w | w Î S* та (q0, w) |=* (q, e), q Î F }
На практиці, при визначенні скінченого автомата М, використовують декілька способів визначення функції d, наприклад:
- це табличне визначення d;
- діаграма проходів скінченого автомата.
Табличне визначення функції d - це таблиця М(qi,aj), де aj Î S, qi Î Q, тобто
М(qi,aj) = { qk |, qk Î d(qi,aj ) }
Діаграма переходів скінченого автомата М - це невпорядкований граф G(V, P), де V – множина вершин графа, а P – множина орієнтованих дуг, причому з вершини qi у вершину qj веде дуга позначена ak , коли qjÎd(qi,ak ). На діаграмі переходів скінченого автомата це позначається так:
ak
qi qj
В подальшому, на діаграмі переходів скінченого автомата М елементи з множини заключних станів будемо позначити так: qi.
Приклад 1. Побудуємо діаграму переходів скінченого автомата М, який розпізнає множину цілочислових констант мови С.
U, u
1,.., 9 L, l
1,.., 9 U, u L,l
 |
q0 0,.., 7
L, l U, u
0 0,.., 7
U, u L, l
 |
A,.., F,a,.., f, 0,.., 9
X, x
 | |||
 |
A,.. F, U, u L, l
a,.., f, L, l
0,.., 9 U, u
Мал. 1.
З побудованого прикладу видно, що приведений автомат не повністю визначений.
Означення. Скінчений автомат М називається детермінованим, якщо d(qi, ak) містить не більше одного стану для любого qi Î Q та ak Î S.
Твердження: Для довільного недетермінованого скінченого автомата М можна побудувати еквівалентний йому детермінований скінчений автомат М1, такий що
L(M) = L(M1).
Доведення: Нехай М – недетермінований скінчений автомат, такий що
М=< Q, S, d, q0, F>
Детермінований автомат М1=< Q1, S, d1, q01, F1> побудуємо таким чином:
1. Q1 = P (Q), тобто імена станів автомата М1 – це підмножини множини Q.
2. q01= { q0 }, { q0 } Î P (Q).
3. F1 складається з усіх таких підмножин S Î P (Q), таких що S Ç А ¹ Æ.
4. d1(S, a) = {q | q Î d(qi, a), qi Î S }.
Доведемо індукцією по i, що (S,w) |=i (S1,e), тоді і тільки тоді, коли
S1= { q | (qi, w)) |=i (q, e), для qi Î S },
Зокрема, ({q0}, w) |=* (S1, e), для деякого S1 Î F1, тоді і тільки тоді, коли
(q0, w) |=* (q, e), q Î F. Таким чином, L(M) = L(M1).
Побудований нами автомат М має дві властивості: він детермінований та повністю визначений. До того ж кількість станів цього автомата 2n – 1.
