8299308032

Definicja 1.3

Przez język automatu skończonego A rozumiemy zbiór L(A) wszystkich słów akceptowanych przez ten automat.

Przykład 1.4

Językiem automatu A z przykładu 1.2 jest język L(A) złożony ze słów postaci W1CW2C ... w_nc

gdzie każde Wi ma postać    ab.. . ab

wielokrotnie powtórzone

□

Dla danego alfabetu E łatwo skonstruować automaty definiujące

•    język pusty, niezawierający żadnego słowa (ozn. 0);

•    język pełny, zawierający wszystkie słowa dające się napisać literami z E (ozn. E*);

•    dla każdego skończonego zbioru słów w 1,... ,w_n G E*, język skończony, składający się dokładnie ze słów wi,... ,w_n (ozn. {tui,..., u?_n}).

Jak widać z przykładu 1.4, język nieskończony różny od pełnego też może być definiowany automatem skończonym; ale istnieją języki nieskończone, do których nie istnieją automaty definiujące. Najprostszymi przykładami są te, w których istnieją jakieś nietrywialne zależności arytmetyczne między liczbami występujących w nich liter.

Przykład 1.5

Język | fc > 0 j ⁵, który składa się ze słów zaczynających się od ciągu liter a i kończących się ciągiem liter b tej samej długości, nie jest definiowany żadnym automatem skończonym.

□

Definicja 1.6

Językiem regularnym nazywamy zbiór słów definiowany jakimś automatem skończonym.

Języki programowania komputerów nie są regularne — do ich analizowania potrzeba narzędzi bardziej skomplikowanych niż automaty skończone. Ale do samego sprawdzenia, czy podstawowe jednostki programu komputerowego, takie jak słowa kluczowe, identyfikatory, liczby itp., są napisane poprawnie, wykorzystuje się automaty skończone, bo język, złożony z dopuszczalnych jednostek podstawowych, jest regularny. Regularne są też języki definiowane wzorcami, do których mają pasować słowa; do ich analizy też wystarczy używać automatów.

⁵ Górny indeks przy literze oznacza liczbę powtórzeń litery; np. b⁴ oznacza słowo bbbb. Konsekwentnie, b^k oznacza słowo b... b.

6