Podręcznik

1. Pojęcia podstawowe

1.1. Alfabet

Alfabet to dowolny niepusty zbiór skończony V (niekiedy dodajemy zbiór symboli lub zbiór liter). Elementy alfabetu nazywamy literami lub symbolami. Alfabet tak jak zbiór oznaczamy najczęściej dużymi literami alfabetu łacińskiego np. V, A itd.

Alfabet binarny (inaczej alfabet dwójkowy) to alfabet złożony z 2 elementów: np. V = {0, 1}, V = {L, H}.

Alfabetami są zbiory skończone: V = {a, b, c}, V = {0, 1, 2, ..., 9}, V = {a, b, c, ..., x, y, z},
V = {a, b, c, ..., x, y, z, A, B, C, 0, 1, 2, ..., 9}

Przy formalnym opisie języka programowania pierwszym krokiem jest zawsze sprecyzowanie skończonego zbioru symboli czyli alfabetu, którym będziemy się posługiwać. Podanie, sprecyzowanie alfabetu (a ściślej alfabetów) powinno stanowić również zawsze pierwszy krok w definicji automatu skończonego, czy też w definicji kodu. Pojęcia kodu i automatu skończonego będą omawiane w dalszej części wykładu.

Warto zwrócić uwagę, na fakt że to co nazywamy symbolem lub literą jest kwestią umowy. W systemach cyfrowych symbole często utożsamiamy z pewnymi łatwo rozróżnialnymi sytuacjami fizycznymi, stanami układu fizycznego np. stanami układu elektronicznego zwanego przerzutnikiem bistabilnym (układ przerzutnika bistabilnego ma 2 łatwo rozróżnialne stabilne stany).

Dla nas symbolem będzie np. wartość napięcia w określonym węźle układu cyfrowego (H - wyższe napięcie np. 5 V lub L - niższe napięcie np. 0 V) a alfabetem zbiór V = {L, H}. Typowe wartości napięcia H i L w systemach cyfrowych to H = 5 V i L = 0 V (np. tak jest w tzw. układach TTL i CMOS o małej skali scalenia) ale wewnątrz układu scalonego o dużej skali scalenia stosuje się z reguły napięcia niższe np. H = 3,3 V, L = 0 V. Oczywiście rozsądek techniczny każe uznawać za napięcie H wszystkie wartości napięć z pewnego niewielkiego przedziału I_H zawierającego nominalną wartość napięcia H (czyli napięcia zbliżone do H) i podobnie za napięcie L przyjmujemy wszystkie napięcia z niewielkiego przedziału I_L zawierającego nominalną wartość napięcia L (czyli napięcia zbliżone do L). Musimy przy tym spełnić oczywiście warunek by I_H∩ L_H = 0.

Symbolem może być również przemagnesowanie określonego miejsca nośnika magnetycznego lub brak takiego przemagnesowania. Uzyskujemy w tej sytuacji 2 symbole, które łatwo możemy zapisywać na powierzchni magnetycznej za pomocą tzw. głowicy magnetycznej.

Symbolem może być też drobne wgłębienie na powierzchni CD-ROM-u (tzw. pit) rozpraszający światło promienia lasera głowicy odczytującej lub brak pit-u na powierzchni CD-ROM-u powodujący odbicie promienia laserowego. Odbity promień lasera trafia do detektora (diody detekcyjnej) wywołując impuls elektryczny odpowiadający 1.

Symbolem może być również stan przełącznika mechanicznego o 2 (czy ogólnie n pozycjach stabilnych).

Cechą charakterystyczną symboli czyli liter wchodzących w skład alfabetu jest łatwość ich zapisywania (czyli zapamiętywania) i odczytywania bez pomyłek. Stąd zresztą popularność w praktyce alfabetu binarnego. Układ fizyczny mający tylko dwa dobrze wyodrębnione stany utożsamiane odpowiednio z 0 lub 1 okazuje się w praktyce pewniejszy, bardziej niezawodny.

Reasumując, powyżej opisaliśmy 4 najczęściej stosowane sposoby reprezentacji w systemach cyfrowych symboli 0 i 1 :

sposób elektryczny wykorzystujący 2 poziomy napięcia L i H w określonym węźle układu elektronicznego (jest to tzw. kodowanie potencjałowe „0” i „1”)
sposób magnetyczny wykorzystujący przemagnesowanie nośnika magnetycznego
sposób optyczny wykorzystujący zmianę własności optycznych powierzchni odbijającej światło laserowe
sposób mechaniczny wykorzystujący stan przełącznika mechanicznego.

Istota rzeczy: Właściwie pojęcie alfabetu jest intuicyjnie jasne a rola dokładnie taka sama jaką pełni alfabet w języku naturalnym. Alfabet służy do zapisywania słów. Warto zwrócić uwagę, na fakt, że to co nazywamy symbolem w formalnej definicji alfabetu jest oczywiście kwestią umowy.