Pok-2-wyk-Slajd6
Alfabet, napis, język
Zdefiniujmy pojęcia, których używać będziemy w dalszej części wykładu.
Termin alfabet lub słownik oznacza dowolny niepusty i skończony zbiór symboli. Najbardziej typowymi przykładami symboli są litery, cyfry oraz znaki specjalne. Przykładem alfabetu może być alfabet binarny składający się z dwóch symboli 0 oraz 1.
Innym alfabetem może być zbiór znaków ASCII.
Napis nad pewnym alfabetem to skończona sekwencja symboli z tego alfabetu.
Przykładem napisu nad alfabetem binarnym będzie dowolna liczba zapisana w systemie binarnym, na przykład liczba 101. Innym przykładem, napisu, tym razem nad alfabetem znaków ASCII będzie słowo kluczowe „return”.
Długość napisu „w” oznaczana jako |w| jest liczbą symboli występujących w napisie „w”. Zgodnie z tą konwencją długość napisu „101” to 3, podczas gdy długość napisu „return” to 6.
Napis pusty oznaczamy za pomocą symbolu epsilon.
Język to dowolny zbiór napisów nad pewnym ustalonym alfabetem. Przykładem języka jest zbiór wszystkich liczb zapisanych w systemie binarnym.
