3813100541

Podstawowe definicje

Poniższe definicje są ogólnie znane.

Definicja 1. Alfabetem nazywamy dowolny, skończony zbiór symboli.

Definicja 2. Niech E będzie alfabetem. Słowem nad alfabetem E nazywamy skończony ciąg symboli z tego alfabetu.

Definicja 3. Niech E będzie alfabetem. Zbiór

E* = {(Tl(72 • • • (7_m|(7i, (72, . . . , (7_m € E, 771 € N U {0}}

jest zbiorem wszystkich możliwych słów nad alfabetem E.

Definicja 4. H-językiem, bądź językiem nazywamy każdy podzbiór zbioru E* wszystkich słów nad alfabetem E.

Wprowadźmy następujące oznaczenia: uj - zbiór liczb naturalnych, uj+ - zbiór liczb naturalnych bez zera.

Definicja 5. Niech E będzie alfabetem. Zbiór E^w jest zbiorem wszystkich możliwych nieskończonych ciągów symboli z alfabetu E. Elementy tego zbioru nazywamy uj-słowami.

Definicja 6. uj-Językiem nazywamy każdy podzbiór zbioru E^.

Niech S będzie dowolnym zbiorem. Dla dowolnych dwóch ciągów r € S* i s € S* U piszemy r C s, gdy r jest podciągiem s, tzn. ciąg s jest nie krótszy niż ciąg r oraz € {1,..., ti} rj = s*.

5