4130649344

Rozdział 1

Podstawowe pojęcia i oznaczenia

1.1. Automaty skończone na słowach

Punktem wyjścia do rozważań dotyczących drzew będą słowa skończone oraz automaty skończone na nich działające. Ponieważ w literaturze stosowane są różne wersje definicji i różne oznaczenia wypiszemy w tym rozdziale definicje pojęć, na które się będziemy później wielokrotnie powoływać.

Załóżmy, że E jest skończonym zbiorem symboli (alfabetem). Przez E¹ będziemy oznaczać zbiór wszystkich słów skończonych nad alfabetem E. Ponieważ w niniejszej pracy zajmujemy się tylko skończonymi słowami, od tej chwili będziemy pomijali przymiotnik „skończony” w tym kontekście. Tak więc w dalszej części pracy „słowo” oznacza zawsze „słowo skończone”.

Definicja 1.1.1 Niedeterministycznym automatem skończonym (lub w skrócie automatem skończonym) na słowach (NFA — z ang. Nondeterministic Finite Automaton) nazywamy obiekt postaci A = (Q, E, ó, I, F), gdzie:

•    Q jest skończonym zbiorem stanów,

•    E jest skończonym alfabetem,

•    5 C Q x E x Q jest relacją przejścia,

•    I QQ to zbiór stanów początkowych,

•    F C Q to zbiór stanów akceptujących.

Bieg automatu A na słowie w — a%a2 ■ ■ ■ a_n to taki ciąg stanów p = qqq\ ■ ■ - Qn, że qo G I oraz dla i = 1,2,... ,n istnieje przejście automatu A ze stanu qi-i do qi po literze a;, to znaczy {q,~i, ai, qi) € ó. Bieg p jest akceptujący jeżeli q_n € F. Jeżeli istnieje bieg akceptujący automatu A na słowie w to mówimy, że A akceptuje w.

Przez L(A) będziemy oznaczać język wszystkich słów akceptowanych przez automat A. Powiemy, że automat A rozpoznaje język L C E¹ jeżeli L = L(A).

Będziemy wykorzystywać strzałkową notację dla przejść i pisać p q zamiast (p, a, q) € 5 jeżeli z kontekstu będzie jednoznacznie wynikało o jaką relację przejścia chodzi.

Często wygodnie jest korzystać z rozszerzenia relacji przejścia S z liter na słowa. I tak niech 5¹ : Q x E¹ x Q będzie najmniejszą taką relacją, że:

7

1

   (?) £> q) ^ dla każdego q&Q,