img191

Dodatek 3

Podstawowe pojęcia teorii języków formalnych i automatów

Podstawowe pojęcia teorii języków formalnych zostały zdefiniowane w połowie lat pięćdziesiątych przez Noama Chomsky’ego w pracach związanych z badaniem matematycznych modeli gramatyk opisujących języki naturalne [21] (jakkolwiek gramatyki Chomsky’ego można traktować jako podsystemy Thue’go, norweskiego matematyka żyjącego w latach 1863-1922). Co prawda później okazało się, że zastosowanie teorii Chomsky’ego w lingwistyce ma stosunkowo ograniczony zasięg, ale stworzone przez niego pojęcia są niezwykle przydatne w tak podstawowych dziedzinach informatyki, jak: języki programowania, projektowanie kompilatorów, czy właśnie rozpoznawanie obrazów.

Wprowadźmy następujące pojęcia.

Alfabetem E nazywamy pewien skończony zbiór symboli.

Ciągiem (słowem, zdaniem) nad alfabetem E nazywamy każdy ciąg skończonej długości składający się z symboli alfabetu E.

Przykładowo, dla alfabetu E = {a, 6), następujące napisy są słowami nad E : a, 6, aa, ab,ba,bb, aaa, aab,... Zbiór wszystkich ciągów nad alfabetem E oznaczamy przez E⁺, tzn. E⁺ = {a,b,aa,ab,bb,...} dla E = {a, t}.

Słowo nie składające się z żadnego symbolu jest określone jako słowo puste i jest oznaczane przez A. Wprowadźmy oznaczenie E' = E⁺ U {A}.

Przedstawiając definicję ciągowej gramatyki formalnej, dokonuje się zwykle następującego podziału na cztery klasy gramatyk według klasyfikacji Chomsky’ego.

Ciągową gramatyką formalną (gramatyką ciągową, gramatyką) nazywamy czwórkę:

<9 = (E/v,Et,P,S),

gdzie: E^ - zbiór symboli nieterminalnych, Et - zbiór symboli terminalnych, P - zbiór produkcji (reguł przepisujących), S - symbol startowy, S € E p/.