Скінченні автомати. Методика побудови лексичного аналізатора на основі скінченного автомата

Недетмінований ск. автомат – це п‘ятірка M=(Q, S, d, q₀, F), де Q – ск. множ. станів, S - ск. множ. дозволених вх. симв., d: Q x S -> B(Q) - функція переходів, q₀ÎQ– початковий стан, F ÍQ – множ. заключних станів.

Роботою скін. авт. є деяка послід. кроків, або тактів. Такт задається поточним станом автомату та вхідним символом, який він бачить на зараз на вхідній ленті. Сам такт складається із зміни стану та здвигу вхідної головки на одну ячейку праворуч.

Пара (q, w) ÎQxS* - є конфігурація автомату. (q0, w) – початкова конфігурація, (q, e), qÎF – заключна конфігурація (або допустима). Такт автомату є бінарне відн. ½¾M заданих на конфігураціях: якщо
d (q, a) ' q’, то (q, aw) ½¾ M (q’, w) для " wÎS*.

Мова, яку задає (розпізнає) автомат M: L(M) = {w | wÎS* та (q0, w) ½¾ * (q,e) для деякого qÎF}

Засоби завдання ск. автоматів:

· табличний – задаємо таблицею ф‑ю d,

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

· матричний – будуємо вектори 1:n [вхідні компоненти 1:k + вихідні компоненти k:n], цим задаємо зв‘язок вхідних даних з вихідними.

Методика побудови лексичного аналізатора: Нехай є ск. автомат M=(Q, S, d, q₀, F, Err), де Err ÍQ – мн. помилкових станів. При своїй роботі авт. (зпочатку знах. в поч. стані q₀) читає з вхідної стрічки символи поки не потрапить в деякий стан q (порожні символи пропускаються, тобто існує перехід по порожньму символу зі стану q₀ в стан q₀): якщо q Î F, то розпізнана деяка лексема (яка саме – залежить від стану, який відповідає лексемі), передаємо її синтаксичному аналізатору та переводимо автомат в стан q₀; якщо q Î Err, то розпізнувана лексема є помилковою -> кінець роботи. Спрощена (!) схема: