Urszula Boryczka
SKRYPT
Uniwersytet Śląski
Wydział Informatyki i Nauki o Materiałach
Wprowadzenie do informatyki
Spis treści
Rozdział 1. Arytmetyka binarna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1. Rozwinięcie dwójkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1. Reguła zamiany . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Dowody zapisu liczb w trzech kodach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3. Dowód zapisu liczb binarnych w postaci ułamkowej . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Przesunięcia liczb binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5. Porównanie operacji dodawania i odejmowania w systemie binarnym w trzech kodach
zapisu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6. Mnożenie liczb binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.1. Metoda bezpośrednia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.2. Metoda Bootha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7. Dzielenie liczb binarnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7.1. Metoda porównawcza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7.2. Metoda nierestytucyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Rozdział 2. Logika binarna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1. Podstawowe zagadnienia logiki binarnej . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2. Definicja algebry Boole a i postulaty Huntingtona . . . . . . . . . . . . . . . . . . . . . . . 26
2.3. Funkcje boolowskie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Rozdział 3. Translacja wyrażeń arytmetycznych . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1. Podstawowe informacje o translacji i translatorach . . . . . . . . . . . . . . . . . . . . . . . 35
3.2. Algorytm translacji wyrażeń na ONP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3. Algorytm przejścia z postaci postfiksowej na postać infiksową . . . . . . . . . . . . . . . . 38
3.4. Algorytm konwersji z instrukcją warunkową . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5. Algorytm translacji zapisu ONP na język symboliczny . . . . . . . . . . . . . . . . . . . . 41
Rozdział 4. Maszyna Turinga i automaty skończone . . . . . . . . . . . . . . . . . . . . . . 43
4.1. Maszyna Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2. Wyrażenia regularne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3. Automaty skończone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.1. Deterministyczny automat skończony . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.2. Niedeterministyczny automat skończony . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.3. Automat skończony z �-ruchami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4. Konstruktory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4.1. Konstruktor diagramu przejść dla sumy teoriomnogościowej r = r1 + r2 . . . . . . 53
4.4.2. Konstruktor dla złożenia r = r1r2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
"
4.4.3. Konstruktor dla domknięcia r = r1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Rozdział 5. Gramatyki i języki formalne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.1. Gramatyki  podstawowe informacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2. Gramatyki bezkontekstowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.3. Język wyrażeń algebraicznych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4. Drzewo wywodu dla gramatyki bezkontekstowej . . . . . . . . . . . . . . . . . . . . . . . . 59
5.5. Klasyfikacja Chomsky ego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Spis tabel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Spis rysunków . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Rozdział 1
Arytmetyka binarna
W tym rozdziale przedstawiony zostanie sposób kodowania liczb binarnych. Ponadto zaprezen-
towana będzie reguła zamiany z jednego systemu liczenia na inny (np. z systemu dwójkowego
na czwórkowy). Zostaną zaprezentowane także trzy kody zapisu liczby binarnej. Podane zo-
staną również algorytmy podstawowych operacji arytmetycznych (tj. dodawania, odejmowania,
mnożenia oraz dzielenia), jakie można wykonać na liczbach binarnych wraz z ich dowodami.
Algorytmy te zostaną poparte przykładami.
1.1. Rozwinięcie dwójkowe
Najpopularniejszym sposobem kodowania informacji zawartych w liczbach jest kodowanie infor-
macji w pozycyjnym systemie dziesiętnym. W systemie tym, aby przedstawić liczbę naturalną
używa się symboli: dziesięciu cyfr od 0 do 9. Jeśli natomiast chcemy przedstawić liczbę całkowitą
musimy również użyć 10 cyfr (0. . . 9); dodatkowo wykorzystujemy znak  minus i  plus oraz
znak  przecinka , który oddziela część całkowitą od ułamkowej.
W systemie dwójkowym natomiast znak  kropki oddziela bit znakowy od części całkowitej
liczby, natomiast znak  przecinka podobnie jak w systemie dziesiętnym oddziela część cał-
kowitą od ułamkowej. W niektórych sytuacjach, stosuje się skrócony zapis liczb binarnych 
wtedy bezpośrednio po bicie znakowym następuje kropka, a po niej cyfry części ułamkowej.
Część całkowita w takich przypadkach jest równa zero; w zapisie jest ona pomijana (formalnie
rzecz biorąc, po bicie znakowym powinna nastąpić kropka, potem zero, następnie przecinek, a
na końcu dopiero cyfry części ułamkowej).
Istnieje wiele systemów kodowania liczb, z jakimi stykamy się na co dzień, jednak to ko-
dowanie w systemie binarnym jest najbardziej rozpowszechnione wśród sposobów kodowania
(rzecz jasna w informatyce), ze względu na przystosowanie urządzeń informatycznych do pra-
cy z ciągami kodowymi w elektronicznych systemach liczących. Liczby w takich systemach są
przedstawiane jako ciągi zer i jedynek. Wśród kodowania binarnego możemy rozróżnić dwa
rodzaje kodowania.
Pierwszy sposób to dwójkowe kodowanie cyfr rozwinięcia pozycyjnego (jest to tzw. kod BCD,
ang. Binary Coded Decimal), w którym poszczególnej cyfrze dziesiętnej przyporządkowujemy
odpowiedni ciąg zer i jedynek.
Drugim natomiast sposobem jest dwójkowy system pozycyjny, czyli przedstawienie liczb
w systemie pozycyjnym o podstawie dwa. Dwójkowy system pozycyjny to system dwóch znaków
 dwóch cyfr 0 i 1. Cyfry dwójkowe nazywamy również cyframi binarnymi (z ang. Binary Digit).
n-1

L(A) = ai � 2i - suma arytmetyczna
i=-m
Wyróżniamy dwa sposoby zapisu liczb:
1. Każda cyfra może przybierać różne wartości w zależności od jej położenia w liczbie (system
pozycyjny).
2. System niepozycyjny, w którym wartość cyfr nie zależy od ich pozycji w liczbie (np. cyfry
rzymskie).
6 Rozdział 1. Arytmetyka binarna
Rysunek 1.1. Kod pozycyjny, system dziesiętny
W systemie pozycyjnym odpowiednim położeniom cyfry w liczbie są przyporządkowane od-
powiednie  wagi , które informują o wartości nominalnej cyfry w liczbie. Owe  wagi to kolejne
naturalne potęgi dowolnej liczby [1]. Od liczby, jaka jest  wagą pochodzi nazwa np: dla 2,
system o podstawie potęgi 2 będzie nosił nazwę dwójkowego.
1.1.1. Reguła zamiany
Aby zamienić liczbę całkowitą przedstawioną w systemie liczbowym o podstawie liczenia p na
liczbę przedstawioną w systemie liczenia o podstawie q, dzielimy tę liczbę przez q zapisaną w
systemie o podstawie p, aż do otrzymania reszty mniejszej od q. Otrzymane reszty częściowe1
zamienia się na system o podstawie q natomiast dzielenie wykonuje się w systemie o podstawie p.
Dla ułamkowych części liczb algorytm ten jest podobny, z tym, że zamiast dzielenia wy-
konujemy mnożenie. Kolejno otrzymane części całkowite są cyframi nowej liczby w systemie
liczenia o podstawie q. Czynność mnożenia wykonujemy tak długo, aż wyzerujemy część ułam-
kową. W innym przypadku otrzymamy k-ty redukt rozwinięcia, gdzie k oznacza dokładność
wykonywanych obliczeń.
Aby zamienić liczbę całkowitą przedstawioną w systemie liczbowym o podstawie p na liczbę
przedstawioną w systemie liczbowym o podstawie q, gdzie q = pn, grupujemy na prawo i na
lewo od przecinka cyfry liczby, którą dekodujemy i każdą z tych grup dekodujemy oddzielnie.
Zatem każdą z cyfr systemu zapisujemy jako n-cyfrową liczbę w systemie liczenia o podsta-
wie q. Poniżej przedstawiamy przykłady zamian liczb z dziesiętnego systemu liczenia na binarny,
czwórkowy oraz szesnastkowy.
Przykład 1. p = 3, n = 2 m = 2
Najpierw zamienimy liczbę z systemu trójkowego na dziesiętny.
(2 1 , 2 2)3
31 30 3-1 3-2
2 2
L(A)3 = 2 � 3-2 + 2 � 3-1 + 1 � 30 + 2 � 31 = + + 1 + 6 = 78
9 3 9
Przykład 2. Poniżej zostanie pokazany sposób rozpisania liczby dziesiętnej na system dwójko-
wy:
(33,125)10 p q
1
Reszty otrzymane z kolejnych dzieleń
1.2. Dowody zapisu liczb w trzech kodach 7
Część całkowita:
33 : 2 1

16 : 2 0
ćł
ćł
8 : 2 0 spisujemy ćł
ćł
4 : 2 0
2 : 2 0
Część całkowita: 0. 1 0 0 0 0 1
Przykład 3. Część ułamkowa:
0,125 � 2 0
ćł
ćł
0,250 � 2 0
ćł
ćł
0,500 � 2 1 spisujemy
0
0 . 0 0 1
Część ułamkowa:
1 1 1
2 4 8
Przykład 4. Zamiana z systemu liczenia o podstawie 2 na system liczenia o podstawie 4
q = pn
p = 2
q = 4
(1 11 01 01 11 01)2
20 21 + 20 21 + 20 21 + 20 21 + 20 21 + 20
Grupujemy: 01 zatem 1 � 20 = 1
11 zatem 1 � 21 + 1 � 20 = 3
01 zatem 0 � 21 + 1 � 20 = 1
01 zatem 0 � 21 + 1 � 20 = 1
11 zatem 1 � 21 + 1 � 20 = 3
01 zatem 0 � 21 + 1 � 20 = 1
stąd otrzymujemy liczbę zapisaną w kodzie czwórkowym: (1 3 1 1.3 1)4
Przykład 5. Zamiana z systemu liczenia o podstawie 16 na system liczenia o podstawie 4
q = 4; p = 16; q, n = -2
10  A, 11  B, 12  C, 13  D , 14  E, 15  F.
(7 5 D)16 Zatem poszczególne cyfry liczby dzielimy z resztą przez podstawę nowego systemu
7 5 13
liczenia i zapisujemy na dwóch miejscach, tj.: = 1 reszty 3; = 1 reszty 1 oraz D, czyli =
4 4 4
3 reszty 1.
Stąd otrzymujemy liczbęw systemie liczenia o podstawie 4: (1 3 1 1. 3 1)4
1.2. Dowody zapisu liczb w trzech kodach
W tej części naszej pracy zaprezentujemy zapis liczby binarnej w trzech kodach:
Kod Znak Moduł
n-2

L(A) = r(an-1) + ai � 2i
i=-m
r(an-1) = 1 - 2 � an-1
8 Rozdział 1. Arytmetyka binarna
Kod Uzupełnienie do 1 (ZU1)
n-2

L(A) = -an-1 � (2n-1 - 2-m + ai � 2i
i=-m
gdzie an-1 oznacza bit znakowy.
Gdy bit znakowy równa się zero (liczba dodatnia), wtedy powyższy wzór wygląda następu-
jąco:
n-2 n-2

L(A) = 0 � (2n-1 - 2-m) + ai � 2i = ai � 2i
i=-m i=-m
W kodzie ZU1 liczba ujemna otrzymywana jest przez zanegowanie poszczególnych pozycji
z kodu ZM, czyli: aiZU1 = aiZM = 1 - aiZM .
Ponadto jej bit znakowy jest równy jeden. Uwzględniając te założenia zapis tej liczby w ko-
dzie ZU1 wygląda następująco:
n-2


L(A) = -1 � (2n-1 - 2-m) + aiZU2 � 2i
i=-m
n-2


= -1 � (2n-1 - 2-m) + (1 - aiZM ) � 2i
i=-m
n-2


= - 2n-1 - 2-m + 2i - 2i � aiZM
i=-m
n-2 n-2

= -2n-1 + 2-m + 2i - 2i � aiZM
i=-m i=-m
n-2

= -2n-1 + 2-m + 2n-1 - 2-m - 2i � aiZM
i=-m
n-2

= - 2i � aiZM
i=-m
Kud uzupełnienia do 2 (ZU2) W kodzie ZU2 liczba ujemna otrzymywana jest przez za-
negowanie wszystkich pozycji, oprócz jedynki na najmniej znaczącej pozycji w liczbie, czyli
aiZU2 = aiZM + 2-m = 1 - aiZM + 2-m
Dana jest liczba:
n-2

L(A) = -an-1 � 2n-1 + aiZU2 � 2i
i=-m
Udowodnienie poprawności zapisu tej liczby jest natępujące:
1. Dla przypadku, gdy an-1 = 0 liczba ma postać taką samą jak w ZM.
1.3. Dowód zapisu liczb binarnych w postaci ułamkowej 9
2. Dla przypadku, gdy an-1 = 1:
n-2

L(A) = -1 � 2n-1 + aiZU2
i=-m
n-2


= -2n-1 + (1 - aZM ) � 2i + 2-m
i=-m
n-2 n-2


= -2n-1 + 2i - 2i � aZM + 2-m
i=-m i=-m
n-2

= -2n-1 + 2-m + 2n-1 - 2m - 2i � aZM
i=-m
n-2

= - 2i � aZM
i=-m
Wyjaśnienie W obu przypadkach wątpliwości może budzić przekształcenie:
n-2

2i = 2n-1 - 2m
i=-m
Równość rzeczywiście zachodzi, jako, że nie jest to nic innego jak rachunek na liczbach binarnych.
Zamiast pisać ciąg (m+n-2) jedynek, można w sposób skrócony zapisać liczbę jako jedynkę na
pozycji bitu znakowego n - 1, (m + n - 1) zer, a następnie odjąć jedynkę na najmniej znaczącej
pozycji 2-m.
1.3. Dowód zapisu liczb binarnych w postaci ułamkowej
Dana jest liczba w systemie o podstawie p: (A)p = an-l, an-2, . . . , a1, a0, a-1, . . . a-m = (C)p, (U)p
gdzie:
 (C)p  część całkowita liczby (A)p,
 (U)p  część ułamkowa liczby (A)p,
oraz dane są zasady relacji dla operacji arytmetycznych na liczbach w tym systemie. Przedsta-
wimy liczbę C w systemie o podstawie s:
(A)s = (C)s, (U)s
takie, aby (C)s = (C)p
(A)p = an-1, . . . , a1, a0, a-1, . . . , a-m = (C)p, (U)p
(C)p  część całkowita liczby (A)p
(U)p  część ułamkowa liczby (A)p
a "< 0, 1, . . . , p - 1 >
i
(A)s = (A)p
(A)s = (C)s, (U)s
(C)s = (C)p
(C)p a0
= I0 +
S S
10 Rozdział 1. Arytmetyka binarna
Jeżeli (C)p jest liczbą całkowitą przedstawioną w systemie o podstawie p, to jej odpowiednikiem
w systemie o podstawie s jest liczba:
(C)s = (a , a , . . . , a , . . . , a , a )s
r-1 r-2 i 1 0
Cyframi a (a " {0, 1, . . . , s - 1}) są reszty otrzymane z kolejnego dzielenia przez s w systemie
i i
o podstawie p odpowiednio części całkowitej (C)p i kolejnych ilorazów Ii, aż do uzyskania ilorazu
Ir-1 = 0, zgodnie z poniższym schematem:
(C)p a
0
= I0 +
s s
(I)0 a
1
= I1 +
s s
.
.
.
(I)i a
i+1
= Ii+1 +
s s
.
.
.
(I)r-2 a
r-1
= Ir-1 +
s s
(I)r-2 a
r-1
= 0 +
s s
Uzasadnienie:
Obliczając z poniższego wzoru:
(C)p = sI0 + a
0
Przy uwzględnieniu, że Ii = sIi+1 + a , dla i = 0, 1, . . . , r - 2 otrzymuje się:
i+1
(C)p = a + sI0
0
= a 0 + a 1s + I1s2
. . .
= a + a s + a s2 + . . . + ar-1sr-1 + Ir-1sr-1
0 1 2
= a + a s + a s2 + . . . + ar-1sr-1 = (C)s
0 1 2
Dana jest liczba o podstawie p (A)p = an-1, . . . , a0, a-1, . . . a-m = (C)p, (U)p gdzie:
 C - część całkowita
 U - część ułamkowa
Należy znalez
ć przedstawienie liczby A w systemie o podstawie p (A) = (C), (U), takie, aby
(U)s = (U)p (uwzględniając przypadek reduktu rozwinięcia).
(A)p = an-1, . . . , a1, a0, a-1, . . . , a-m = (C)p, (U)p
Zakładamy:
 (C)p - część całkowita liczby (A)p
 (U)p - część całkowita liczby (A)p
a "< 0, 1, . . . , p - 1)
i
(A)s = (C)s, (U)s
(U)s = (U)p
1.4. Przesunięcia liczb binarnych 11
Jeżeli (U)p jest liczbą ułamkową, przedstawioną w systemie o podstawie p, to jej odpowiednikiem
w systemie o podstawie s jest liczba:
(U)s = (0, a , . . . , a , a , a , . . . , a )s + d r
n-1 1 0 -1 -m
gdzie d r = �rs-r - błąd zaokrąglenia (� < 1) Cyfry a (a " {0, 1, . . . , s-1}) są cyframi
-i -i
przeniesienia przechodzącym na część całkowitą, otrzymanymi z kolejnego pomnożenia przez
s liczby w systemie o podstawie p odpowiednio części ułamkowej (U)p i kolejno uzyskiwanych
ułamków, aż do uzyskania wymaganej liczby cyfr lub wartości zero ułamka Ir, zgodnie z nastę-
pującym schematem:
(U)ps = I1 + a
-1
I1s = I2 + a
-2
.
.
.
Iis = Ii+1 + a
-i-1
.
.
.
Ir-2s = Ir-1 + a
-r+1
Ir-1s = Ir + a
-r
= �r + a
-r
Można obliczyć na podstawie powyższych wzorów:
(U)p = a s-1 + I1s-1
-1
uwzględniając
Ii = Ii+1s-1 + a s-1 dla i = 0, 1, . . . , r - 1
-i-1
Podstawiając uzyskujemy:
(U)p = a s-1 + I1s-1
-1
= a s-1 + a s-2 + I2s-2
-1 -2
. . .
= a s-1 + a s-2 + a s-3 + . . . + a s-r + I-rs-r
-1 -2 -3 -r
= a s-1 + a s-2 + a s-3 + . . . + a s-r + �rs-r
-1 -2 -3 -r
= (U)s
Podobne przekształcenia można znalez
ć w [2].
1.4. Przesunięcia liczb binarnych
Poniżej przedstawiamy tabelę przesunięć liczb binarnych w trzech kodach zapisu.
Aby pomnożyć liczbę przez 2i - należy przesunąć ją o  i pozycji w lewo.
Aby podzielić liczbę przez 2i (pomnożyć przez 2-i) należy przesunąć ją o  i pozycji w prawo.
Poniższy dowód wyjaśnia, dlaczego podczas wykonywania operacji przesunięcia liczby binar-
nej zapisanej w kodzie ZU2 jej zapis uzupełnia się z lewej strony jedynkami, z prawej zerami.
Dowód ten przeprowadzamy tylko dla ujemnej liczby, ponieważ dodatnia liczba zapisana w tym
kodzie ma taką samą postać, jak liczba zapisana w kodzie ZM.
Dana jest liczba binarna w kodzie ZU2, udowodnimy teraz, że w kodzie ZU2 z lewej strony
uzupełniamy liczbę jedynkami, a z prawej zerami.
12 Rozdział 1. Arytmetyka binarna
CYFRY NIEZNACZ� CE PO STRONIE
OD DODATNIE UJEMNE
LEWEJ PRAWEJ LEWEJ PRAWEJ
ZM 0 0 0 0
ZU1 0 0 1 1
ZU2 0 0 1 0
Tabela 1.1. Tabela przesunięć binarnych dla liczb ujemnych
Liczba w ZU2 ma postać:
n-2

L(A) = -2n-1 + aiZU2 � 2i
i=-m
Dowód dla cyfr z lewej strony. Jeśli pomnożymy tę liczbę przez 2-1, to:
 Bit znakowy się nie zmieni.
 Poszczegóne cyfry przesunięte zostaną o jedno miejsce w prawo.
 Z lewej strony zostanie dopisana cyfra X
Liczba po przesunięciu będzie miała postać:
n-2

L(A) = -2n-1 + aiZU2 � 2i-1 + 2n-2X
i=-m
Liczba w postaci  przesuniętej i liczba pierwotna, pomnożona przez 2-1 są sobie równe. Od tej
równości rozpoczynamy dowód:
n-2 n-2

-2n-1 + ai � 2i-1 + 2n-2X = 2-1(-2n-1 + ai � 2i)
i=-m i=-m
n-2 n-2

-2n-1 + ai � 2i � 2-1 + 2n-2X = -2n-2 + ai � 2i � 2-1
i=-m i=-m
-2n-1 + 2n-2X = -2n-2
2n-2X = -2n-2 + 2n-1|| : 2n-1
2-1X = -2-1 + 1
1 1
X =
2 2
X = 1
Dowód dla cyfr z prawej strony. Jeśli pomnożymy tę liczbę przez 21, to:
 Bit znakowy się nie zmieni.
 Poszczegóne cyfry przesunięte zostaną o jedno miejsce w lewo.
 Z prawej strony zostanie dopisana cyfra X
Liczba po przesunięciu będzie miała postać:
n-2

L(A) = -2n + aiZU2 � 2i+1 + 2-mX
i=-m
1.5. Porównanie operacji dodawania i odejmowania w systemie binarnym w trzech kodach zapisu. 13
Liczba w postaci  przesuniętej i liczba pierwotna, pomnożona przez 21 są sobie równe. Od tej
równości rozpoczynamy dowód:
n-2 n-2

-2n + ai � 2i+1 + 2-mX = 2(-2n-1 + ai � 2i)
i=-m i=-m
n-2 n-2

-2n + 2 ai � 2i + 2-mX = -2n + 2 ai � 2i
i=-m i=-m
2-mX = 0
X = 0
1.5. Porównanie operacji dodawania i odejmowania w systemie binarnym
w trzech kodach zapisu.
OPERACJA ZNAK
OPERACJA ZNAKI LICZB POŻYCZKA
WYKONYWANA WYNIKU
RÓWNE Z" = A" + B"  zn-1 = an-1
DODAWANIE
NIE (w=0) zn-1 = an-1
RÓŻNE Z" = A" - B"
TAK w=1 zn-1 = Źan-1
NIE (w=0) zn-1 = an-1
RÓWNE Z" = A" - B"
ODEJMOWANIE
TAK w=1 zn-1 = Źan-1
RÓŻNE Z" = A" + B"  zn-1 = an-1
Tabela 1.2. Tabela operacji dodawania i odejmowania w trzech kodach zapisu
Legenda:
 Z", A", B"  liczby bez bitów znakowych; moduły liczb,
 zn-1, an-1, bn-1  bity znakowe (1. cyfra),
 w  wskaz
nik pożyczki. Jeśli wskaz
nik pożyczki jest ustawiony na 1, wówczas wynik uzysku-
jemy w uzupełnieniu do 2.
Algorytm postępowania Aby dodać lub odjąć dwie liczby w systemie binarnym w kodzie
ZM należy posłużyć się tabelą nr 1.2 ze strony 13. Jeżeli wystąpiła pożyczka liczba zapisana
będzie w kodzie ZU2 (wskaz
nik pożyczki w=1).
Aby dodać liczby w kodzie ZU1 należy dodać liczby razem z ich bitami znakowymi, jeśli
wystąpi przepełnienie to naley uwzględnić je poprzez dodanie go do najmniej znaczącej pozycji.
Aby odjąć liczby w kodzie ZU1 należy odjąć liczby razem z ich bitami znakowymi, jeśli wystąpi
pożyczka to należy uwzględnić ją poprzez odjęcie jej od najmniej znaczącej pozycji.
Aby dodać liczby w kodzie ZU2 należy dodać liczby razem z ich bitami znakowymi, jeśli
wystąpi przepełnienie nie uwzględniamy go. Aby odjąć liczby w kodzie ZU2 należy odjąć liczby
razem z ich bitami znakowymi, jeśli wystąpi pożyczka nie uwzględniamy jej. Poniżej przedsta-
wiamy przykłady dodawania i odejmowania liczb binarnych w trzech kodach zapisu ZM, ZU1,
ZU2:
Przykład 6. ZM X+Y
W tym kodzie wykonujemy operacje arytmetyczne na liczbach bez bitów znakowych, stąd jeśli
mamy wykonać dodawanie liczb o różnych znakach tak naprawdę należy wykonać ich odejmowa-
nie.
14 Rozdział 1. Arytmetyka binarna
40 15 40
X = Y = X = (0.0101000) X = ,
128 128 128
15
Y = (1.0001111)ZM = (1.1110000)ZU1 = (1.1110001)ZU2 Y =
128
0 1 10 1 1 10
0 1 0 1 0 0 0
- 0 0 0 1 1 1 1
0 0 1 1 0 0 1
1 � 20 + 0 � 21 + 0 � 22 + 1 � 23 + 1 � 24 + 0 � 25 + 0 � 26 1 + 8 + 16 25
(0.0011001)ZM = = =
27 128 128

25
Stąd (0.0011001)2 =
128
10
Przykład 7. ZU1 X+Y
Dodajemy przepełnienie do najmniej znaczącej pozycji.
1 1
0.0 1 0 1 0 0 0
+ 1.1 1 1 0 0 0 0
0.0 0 1 1 0 0 0
+ 1
0.0 0 1 1 0 0 1
1 � 20 + 0 � 21 + 0 � 22 + 1 � 23 + 1 � 24 + 0 � 25 + 0 � 26 1 + 8 + 16 25
(0.0011001)ZU1 = = =
27 128 128

25
Stąd (0.0011001)2 =
128
10
Przykład 8. ZU2 X+Y
Przepełnienia w kodzie ZU2 są ignorowane.
1 1
0.0 1 0 1 0 0 0
+ 1.1 1 1 0 0 0 1
0.0 0 1 1 0 0 1
1 � 20 + 0 � 21 + 0 � 22 + 1 � 23 + 1 � 24 + 0 � 25 + 0 � 26 1 + 8 + 16 25
(0.0011001)ZU2 = = =
27 128 128

25
Stąd (0.0011001)2 =
128
10
13
Dane są: X= (0.0001101)
128
5
Y=- (1.00101)ZM (1.11010)ZU1 (1.11011)ZU2
32
Przykład 9. ZM X-Y
W tym kodzie wykonujemy operacje arytmetyczne na liczbach bez bitów znakowych stąd je-
śli mamy wykonać odejmowanie liczb o różnych znakach, to tak naprawdę należy wykonać ich
dodawanie.
1 1 1
0 0 0 1 1 0 1
+ 0 0 1 0 1 0 0
0 1 0 0 0 0 1
1.6. Mnożenie liczb binarnych 15
1 � 20 + 0 � 21 + 0 � 22 + 0 � 23 + 0 � 24 + 1 � 25 + 0 � 26 1 + 32 33
(0.0100001)ZM = = =
27 128 128

33
Stąd (0.0100001)2 =
128
10
Przykład 10. ZU1 X-Y
Pożyczkę należy odjąć od najmniej znaczącej pozycji.
1 1 10 0 10
0.0 0 0 1 1 0 1
- 1.1 1 0 1 0 1 1
0.0 1 0 0 0 1 0
- 1
0.0 1 0 0 0 0 1
1 � 20 + 0 � 21 + 0 � 22 + 0 � 23 + 0 � 24 + 1 � 25 + 0 � 26 1 + 32 33
(0.0100001)ZU1 = = =
27 128 128

33
Stąd (0.0100001)2 =
128
10
Przykład 11. ZU2 X-Y
Pożyczka w kodzie ZU2 jest ignorowana.
1 1 10
0.0 0 0 1 1 0 1
- 1.1 1 0 1 1 0 0
0.0 1 0 0 0 0 1
1 � 20 + 0 � 21 + 0 � 22 + 0 � 23 + 0 � 24 + 1 � 25 + 0 � 26 1 + 32 33
(0.0100001)ZU1 = = =
27 128 128

33
Stąd (0.0100001)2 =
128
10
1.6. Mnożenie liczb binarnych
Wśród metod mnożenia liczb binarnych możemy wyróżnić metodę bezpośrednią oraz metodę
Bootha w dwóch wariantach. Poniżej prezentujemy ich algorytmy, dowody oraz przykłady.
1.6.1. Metoda bezpośrednia
�ł �ł
n-2

�ł łł
U = A" � B" = A � bi2i
i=-m
Metoda ta polega na wielokrotnym dodawaniu odpowiednio przesuniętej mnożnej. Mnożenie
tą metodą wykonywane jest na modułach liczb  czyli bez bitu znakowego. Poniżej przedsta-
wiamy funkcję realizującą ustalenie znaku wyniku. Jest to suma modulo 2 znaków mnożnej i
mnożnika (XOR).
1.6.2. Metoda Bootha
Algorytm pierwszego wariantu Pierwszy wariant metody Bootha wykonywany jest w ko-
dzie ZU2. Metoda ta polega na analizie par bitów mnożnika. Jeśli badana para bitów mnożnika
16 Rozdział 1. Arytmetyka binarna
an-1 bn-1 Un-1
0 0 0
0 1 1
1 0 1
1 1 0
Tabela 1.3. Tabela funkcji XOR
jest kombinacją  10 , to od iloczynu częściowego2 (który ma wartość 0 na początku algoryt-
mu) odejmujemy mnożną L(A) i przesuwamy wynik o jedno miejsce w prawo. Jeśli badana para
bitów mnożnika to kombinacja  01 wówczas dodajemy mnożną L(A) do iloczynu częściowego,
a następnie przesuwamy wynik o jedno miejsce w prawo. Jeśli natomiast badaną parą bitów
mnożnika jest para  00 lub  11 to nie wykonujemy żadnej operacji tylko przesuwamy wynik
o jedno miejsce w prawo. Jeśli w skład pary wchodzi bit znakowy nie wykonujemy przesunięcia.
Dowód Dana jest liczba:
n-2

L(B) = -bn-12n-1 + bi � 2i
i=-m
Założenie: bi = 2bi - bi
2
Iloczyn powstający w wyniku kolejnych operacji opisanych w algorytmie
1.6. Mnożenie liczb binarnych 17
Uwzględniając powyższe założenie dowód pierwszego wariantu metody Bootha można przed-
stawić następująco:
L(A) - mnożna L(B) - mnożnik
= L(A) � L(B)
n-2

= L(A) � (-bn-1 � 2n-1 + bi � 2i)
i=-m
n-2

= L(A) � (-bn-1 � 2n-1 + (2bi - bi) � 2i)
i=-m
n-2 n-2

= L(A) � (-bn-1 � 2n-1 + 2bi � 2i - bi � 2i)
i=-m i=-m
n-2 n-2

= L(A) � (-bn-1 � 2n-1 + bi � 2i+1 - bi � 2i)
i=-m i=-m
= L(A) � (2-m+1 � b-m - 2-m � b-m
+2-m+2 � b-m+1 - 2-m+1 � b-m+1
+2-m+3 � b-m+2 - 2-m+2 � b-m+2
.
.
.
+2n-2 � bn-3 - 2n-3 � bn-3
+2n-1 � bn-2 - 2n-2 � bn-2
-2n-1 � bn-1)
= L(A) � (2n-1(bn-2 - bn-1)
+2n-2(bn-3 - bn-2)
.
.
.
+2-m+1(b-m - b-m+1)
+2-m(b-m-1 -b-m))

( 0 na najmniej znaczącej pozycji)
n-1

= L(A) � bi � 2i
-m
= L(A) � L(B)
Algorytm drugiego wariantu Drugi wariant metody Bootha wykonywany jest w kodzie ZU2
i tylko dla ułamków właściwych. Na początku przesuwamy mnożną o jedno miejsce w prawo

L(A)
. Badamy ostatni bit mnożnika, jeśli ma on wartość 1 to wówczas dodajemy mnożną do
2
iloczynu częściowego (który na początku algorytmu ma wartość 0); jeśli natomiast bit ten ma
wartość 0  wówczas nie wykonujemy żadnej operacji.
Następnie przystępujemy do badania bitu mnożnika stojącego po lewej od poprzedniego,
przesuwamy również iloczyn częściowy o jedno miejsce w prawo. Wszystkie operacje powtarzamy
do momentu, aż dotrzemy do bitu znakowego. Jeśli do niego dotrzemy, to wówczas badamy jego
wartość: jeśli jest równy 1, to wtedy odejmujemy mnożną od iloczynu częściowego, jeśli ma
wartość 0, to nie wykonujemy żadnej operacji.
Dowód Niech U=L(A)� L(B), gdzie L(A)  mnożna, L(B)  mnożnik, U  iloczyn. Ponadto:
b0  bit znakowy.
18 Rozdział 1. Arytmetyka binarna
Dana jest liczba:
-1

L(B) = -b020 + bi � 2i
i=-m
Jej postać informuje nas, że mnożenie drugim wariantem Bootha stosowane będzie jedynie
podczas mnożenie ułamków.
�ł �ł
-1

�ł łł
U = L (A) � -b020 + bi � 2i
i=-m
-1

U = -L (A) � b020 + L (A) � bi � 2i
i=-m
�ł �ł
-1

L(A) L(A)
�ł łł
U = 2 -b0 � + bi � 2i
2 2
i=-m
Poprawka w drugiej metodzie Bootha. Występowanie poprawki jest określone przez bit
znakowy. Poprawka występuje wtedy gdy bit znakowy jest równy 1. Wtedy do wyniku dodajemy

L(A)
.
2
Poniżej przedstawiamy przykłady dla mnożenia liczb binarnych metodą Bootha.
Przykład 12. Pierwszy wariant.
Mnożenie dwóch liczb I wariantem Bootha polega na badaniu kolejnych par bitów mnożnika.
Zatem zgodnie z metodą badamy pierwszą parą od prawej strony  jest to para  10 , zatem od
iloczynu częściowego (na początku równego 0) odejmujemy mnożną; następnie wynik odejmowa-
nia przesuwamy o jedno miejsce w prawo. Jeśli badaną parą jest para  01 dodajemy do iloczynu
częściowego mnożną i również wykonujemy przesunięcie, jeśli badana para to  11 lub  00 to
wykonujemy tylko przesunięcie. Jeśli natomiast w parze znajduje się bit znakowy to wykonujemy
odpowiednio dodawanie lub odejmowanie, ale nie wykonujemy przesunięcia. Całość (jeśli jest
ujemna) dekodujemy do kodu ZM.
Przykładowo:
3 7
X = - Y =
4 8
X = (1.11)ZM X = (1.01)ZU2
Y = (0.1110)
0 . 0 0  10
 1 . 0 1
- 0 . 1 1
- 0 . 0 1 1  11
- 0 . 0 0 1 1  11
0 . 0 0 0 1 1  01
0 . 0 0 0 1 1
+ 1 . 0 1
1 . 0 1 0 1 1 ZU2
1 . 1 0 1 0 1 ZM
Zatem rozwijając wynik w szereg potęgowy otrzymujemy:
1 � 20 + 0 � 21 + 1 � 22 + 0 � 23 + 1 � 24 1 + 4 + 16 21
(1.10101)ZM = - = - = -
25 32 32
1.7. Dzielenie liczb binarnych 19
Przykład 13. Drugi wariant.
Mnożenie dwóch liczb II wariantem Bootha polega na badaniu pojedynczych bitów mnożnika,
więc zgodnie z metodą jeśli badany bit to 1 do iloczynu częściowego dodajemy przesuniętą dzielną

L(A)
, następnie wynik dodawania przesuwamy o jedno miejsce w prawo. Jeśli badany bit to
2
0 wykonujemy tylko przesunięcie. Jeżeli natomiast badany bit to bit znakowy z wartością 1, to
wykonujemy odejmowanie, ale nie wykonujemy przesunięcia. Jeśli natomiast bit znakowy ma
wartość 0, to nie wykonujemy żadnej operacji. Po zbadaniu wszystkich bitów mnożnika całość
wyniku przesuwamy o jedno miejsce w lewo. Całość (jeśli jest ujemna) dekodujemy do kodu ZM.
Dane są:
3 5
A = B = -
8 16
A
A = (0.011) = 0.0011
2
B = (1.0101)ZM B = (1.1011)ZU2
0 . 0 0 0 0  1
+ 0 . 0 0 1 1
- 0 . 0 0 1 1
0 . 0 0 0 1 1  1
+ 0 . 0 0 1 1 0
- 0 . 0 1 0 0 1
- 0 . 0 0 1 0 0 1  0
0 . 0 0 0 1 0 0 1  1
+ 0 . 0 0 1 1 0 0 0
- 0 . 0 1 0 0 0 0 1
0 . 0 0 1 0 0 0 0 1 b0 =, , 1
- 0 . 0 0 1 1 0
1 . 1 1 1 1 0 0 0 1 ZU2
1 . 0 0 0 0 1 1 1 1 ZM
Zatem rozwijając wynik w szereg potęgowy otrzymujemy:
1 � 20 + 1 � 21 + 1 � 22 + 1 � 23 + 0 � 24 + 0 � 25 + 0 � 26 + 0 � 27
(1.00001111)ZM = =
27
1 + 2 + 4 + 8
= =
128
15
=
128
1.7. Dzielenie liczb binarnych
Wśród metod dzielenia liczb binarnych możemy wyróżnić dwie metody: metodę porównawczą
oraz nierestytucyjną. Poniżej przedstawiamy ich algorytmy, dowody oraz przykłady zadań.
1.7.1. Metoda porównawcza
Dzielenie metodą porównawczą dotyczy liczb zapisanych w kodzie ZM, operacje wykonujemy na
modułach liczb. Znak ilorazu bierzemy z sumy modulo 2 znaków dzielnej i dzielnika (patrz tabela
1.3 na stronie 16). Ponadto musi być spełniony warunek |A| < |B| gdzie A jest dzielnikiem,
a B dzielną; warunek dotyczy liczb całkowitych i ułamków.
Na początku przyjmujemy, że pierwszą resztą częściową jest dzielna. Następnie sprawdzamy,
czy reszta częściowa (ri) jest większa od dzielnika. Jeżeli tak, to zapisujemy, że kolejny (i-ty) bit
20 Rozdział 1. Arytmetyka binarna
ilorazu jest równy jeden, a następnie od obecnej reszty częściowej odejmujemy dzielnik, a całą
różnicę przesuwamy o jedno miejsce w lewo. Tak przesunięta różnica staje się kolejną, (i+1)-szą
resztą częściową.
Jeśli natomiast reszta częściowa (ri) jest mniejsza od dzielnika, to zapisujemy, że kolejny
(i-ty) bit ilorazu jest równy zero. Dodatkowo obecną resztę częściową przesuwamy o jedno
miejsce w lewo  przesunięta staje się kolejną, (i + 1)-szą resztą częściową.
W powyższy sposób postępujemy aż do wyzerowania się reszty częściowej (ri = |B|  wtedy
ostatnim bitem ilorazu jest 1) lub do uzyskania żądanej liczby cyfr ilorazu (w przypadku, gdy
iloraz jest niewymierny lub okresowy).
Dowód: Dla metody porównawczej uzyskane bity ilorazu qi rozpoczynają się od i=1, podczas
gdy pierwsza reszta |r0| = |A|. Kolejne reszty częściowe są następujące:
|r1| = 2|r0| - |q1|B
|r2| = 2|r1| - |q2|B
Jak widać, postępujemy zgodnie z algorytmem podanym powyżej.
Po kilku iteracjach reszt częściowych dochodzimy do następującej reszty:
|ri| = 2|ri-1| - |qi|B
Należy pamiętać, że i oznacza i-tą cyfrę ilorazu:
|qi| = 1, gdy 2|ri-1| B
|qi| = 0, gdy 2|ri-1| B
Dzielenie metodą porównawczą prowadzimy do uzyskania reszty równej zero lub do momentu
otrzymania oczekiwanej przez nas liczby cyfr ilorazu. Obliczenia prowadzi się aż do uzyskania
reszty równej 0 lub otrzymania żądanej i-cyfr ilorazu.
Z wzoru ogólnego na resztę mamy:
|ri| = 2|ri-1| - |qi| � |B| � 2-i
|ri| � 2-i = 2-(i-1)|ri-1| - 2-i � |qi| � |B|
Dla i=1:
|r1| � 2-1 = 20|r0| - 2-1 � |q1| � |B| = |r0| - 2-1 � |q1| � |B| = |A| - 2-1 � |q1| � |B|
Dla i=2:
|r2| � 2-2 = 2-1|r1 - 2-2 � |q2| � |B| = |A| - 2-1 � |q1| � |B| - 2-2 � |q2| � |B|
� � �
Wreszcie dla i=p (gdzie rp  ostatnia reszta częściowa):
|rp| � 2-p = |A| - 2-1 � q1 � |B|
- 2-3 � q3 � |B|
.
.
.
- 2-(p-1) � qp-1 � |B|
- 2-p � qp � |B|
p

|rp| � 2-p = |A| - 2i � qi � |B|
i=1
Jako, że |rp| to ostatnia reszta częściowa, przyrównujemy ją do zera.
p

|A| - 2i � qi � |B| = 0
i=1
1.7. Dzielenie liczb binarnych 21
p

|A| = 2i � qi � |B|
i=1
p

|A|
= 2i � qi
|B|
i=1
Reszta całkowita wynosić będzie:
Rp = |rp| � 2-p
Poniżej przedstawiamy przykład dzielenia dwóch liczb binarnych metodą porównawczą.
Przykład 14. Dzielenie rozpoczynamy od zbadania wielkości dzielnika. Jeśli jest mniejszy od
reszty częściowej, to odejmujemy go od reszty częściowej, a różnicę przesuwamy  wówczas q=1.
Jeśli jednak dzielnik nie jest mniejszy, to q=0 i wykonujemy jedynie przesunięcie.
Przykładowo:
9 3
A = B = -
128 16
A = (0.0001001)ZM B = (1.0011)ZM
r0 0 0 0 1 0 0 1
r1 = 2r0 0 0 1 0 0 1 0 < B q1 = 0
r2 = 2r1 0 1 0 0 1 0 0 > B q2 = 1
r3 = 2r2  0 0 1 1 0 0 0
r3 0 0 0 1 1 0 0
�!- 0 0 1 1 0 0 0 B q3 = 1
 0 0 1 1 0 0 0
= = = = = = =
1 0 1 1 3
Q = = -
q0 q1 q2 q3 8
1.7.2. Metoda nierestytucyjna
Dzielenie metodą nierestytucyjną dotyczy dzielenia ułamków zapisanych w kodzie ZU2. Po-
nadto musi być spełniony następujący warunek: moduł dzielnej musi być mniejszy od modułu
dzielnika: |A| < |B|.
Na początku porównujemy bit znakowy reszty częściowej z bitem znakowym dzielnika. Gdy
bity te mają tą samą wartość, to znaczy  11 lub  00 , wtedy bit ilorazu częściowego qi = 1.
Jeśli bity te są różne, czyli mają wartość  01 lub  10 , to bit ilorazu częściowego qi = 0.
Następnie przesuwamy rejestr reszty częściowej jedno miejsce w lewo.
Kolejnym krokiem algorytmu jest sprawdzenie jakie wartości mają bity kolejnej reszty czę-
ściowej i dzielnika. Jeżeli są one takie same, to qi = 1; odejmujemy wtedy dzielnik od przesuniętej
reszty częściowej. Natomiast jeśli były różne, wtedy qi = 0, a do przesuniętej reszty częściowej
dodajemy dzielnik.
Proces ten kończy się wtedy, kiedy reszta częściowa będzie równa zero lub wtedy, kiedy
otrzymamy żądaną liczbę cyfr w przypadku ilorazu niewymiernego lub okresowego. W ostatnim
kroku tego algorytmu powstaje pseudoiloraz, do którego daje się poprawkę równą p = -1 + 2n.
Wynik końcowy zapisany jest w kodzie ZU2.
Dowód poprawności dzielenia metodą nierestytucyjną wygląda następująco:
i = 0 �! r0 = A
22 Rozdział 1. Arytmetyka binarna
i = 1
r1 = 2 � r0 + (1 - 2 � q1) � B
i = 2
r2 = 2 � r1 + (1 - 2 � q2) � B = 2 � (2 � r0 + (1 - 2 � q1) � B) + (1 - 2 � q2) � B =
= 22 + r0 + 2 � (1 - 2 � q1) � B + (1 - 2 � q2) � B
Po n-iteracjach otrzymujemy:
rn = 2n � r0 - 2n-1(2q1 - 1) � B - 2n-2(2q2 - 1) � B
- � � � - 2-1 � (2qn-1 - 1) � B - 20(2qn - 1) � B � 2-n
rn � 2-n = 2n-n � r0 - 2n-1-n(2q1 - 1) � B - 2n-2-n(2q2 - 1) � B
- � � � - 2-1-n � (2qn-1 - 1) � B - 20-n(2qn - 1) � B
rn � 2-n = 20 � r0 - 2-1(2q1 - 1) � B - 2-2(2q2 - 1) � B
- � � � - 2-1-n � (2qn-1 - 1) � B - 20-n(2qn - 1) � B
rn � 2-n = A - 20q1 � B + 2-1 � B
- 2-1q2 � B + 2-2 � B
- 2-2q3 � B + 2-3 � B
.
.
.
- 2-nqn-1 � B + 2-1-n � B
- 2-n+1qn � B + 2-n � B
-(n-1)
-1

rn � 2-n = A - 2n � qn+1B + 2i � B
0 -n
-(n-1)


rn � 2-n = A - 2n � qn+1B + 1 - 2-n � B
0
-(n-1)


A = rn � 2-n + 2n � qn+1B + -1 + 2-n � B \ B
0
-(n-1)


A rn � 2-n
= 2n � qn+1 + -1 + 2-n +
B B
0
Poniżej przedstawiamy przykład dzielenia dwóch liczb binarnych metodą nierestytucyjną:
Przykład 15. W tej metodzie naszym zadaniem jest badanie znaku dzielnika i kolejnej reszty
częściowej. Jeśli znaki są zgodne to odejmujemy dzielnik, wcześniej jednak przesuwamy resztę
częściową w lewo. Natomiast kiedy znaki są różne wykonujemy dodawanie. Przy zgodnych zna-
kach bit wyniku ma wartość 1 przy różnych 0. Dodatkowo do końcowego wyniku musimy jeszcze
dodać poprawkę -1 + 2-n, n to indeks ostatniej reszty r (w tym przykładzie n=3).
1.7. Dzielenie liczb binarnych 23
15
A = - A = (1.0001111)ZM A = (1.1110001)ZU2
128
3
B = B = (0.011)ZM
8
�!- r0 = A 1 . 1 1 1 0 0 0 1 q0 = 0
1 . 1 1 0 0 0 1
+ 0 . 0 1 1
�!- r1 = 0 . 0 0 1 0 0 1 q1 = 1
0 . 0 1 0 0 1
- 0 . 0 1 1
�!- r2 = 1 . 1 1 1 0 1 q2 = 0
1 . 1 1 0 1
+ 0 . 0 1 1
r3 = 0 . 0 0 1 1 q3 = 1
0 . 0 1 1
- 0 . 0 1 1
=.= = = = = = =
P Q = 0.101
1 15
P = -1 + 2-n = -1 + = - (1.1111)ZM (1.0001)ZU2
16 16
0 .1 0 1
+ 1 .0 0 0 1
(1.1 0 1 1)ZU2
5
Po zdekodowaniu: (1.0101)ZM = -
16
Rozdział 2
Logika binarna
Logika binarna jest działem, zajmującym się zmiennymi logicznymi oraz operacjami logicznymi
wykonywanymi na tych zmiennych. Zmienne binarne oznacza się literami alfabetu. Zmienne te
mogą przyjmować dwie wartości: prawda i fałsz. Wartościom tym możemy przypisać następujące
wartości liczbowe:  0 i  1 , gdzie  1 odpowiada prawdzie, a  0 odpowiada fałszowi. Logika
binarna jest wykorzystywana w celu tworzenia matematycznego opisu przetwarzania informacji.
Wszystkie elementy logiki binarnej przydatne są podczas procesu analizy i projektowania sys-
temów cyfrowych. Przykładem takiego zastosowania logiki binarnej są cyfrowe układy logiczne.
Układy wykonują binarne operacje arytmetyczne. Ich działanie najbardziej obrazowo można
przedstawić jako operacje logiczne przeprowadzane na zmiennych binarnych. Logika binarna
przedstawiona w tym pojęciu jest tożsama z algebrą Boole a
2.1. Podstawowe zagadnienia logiki binarnej
Wyróżniamy trzy podstawowe operacje logiczne:
 koniunkcję (I)
 alternatywę (LUB)
 negację (NIE)
Symbolem, za pomocą którego przedstawiamy operację mnożenia arytmetycznego jest krop-
ka. Symbol ten w zapisie jest często pomijany. Natomiast, jeżeli chodzi o mnożenie jako operację
logiczną (koniunkcję) symbolem jej jest I ('"). Operację tą można przedstawić następująco:
x � y = z, z będzie równe 1 wtedy tylko wtedy, jeśli oba czynniki są równe jeden; w przeciwnym
przypadku z = 0 należy również pamiętać, że wszystkie elementy tego wyrażenia x, y, z są
zmiennymi binarnymi, które mogą przyjmować wartości  1 lub  0 .
Operacja iloczynu logicznego:
x y x � y
0 0 0
0 1 0
1 0 0
1 1 1
Tabela 2.1. Tabela operacji iloczynu logicznego
Operację alternatywy przedstawia się za pomocą znaku +. Następujące wyrażenie x + y = z
należy rozumieć w ten sposób: x lub y równe z. Wyrażenie to ma wartość równą  1 w dwóch
przypadkach: x i y są równe 1; x lub y są równe 1 natomiast wyrażenie przyjmuje wartość 0 w
jednym przypadku: x i y są równe 0.
Operacja negacji (NIE) jest przedstawiana wymiennie za pomocą następujących znaków:
 Apostrofu - A
 Kreski poziomej nad zmienną - A
 Znaku negacji - Ź
x = z odczytujemy: nie x jest równe z. Operacja negacji:
26 Rozdział 2. Logika binarna
x y x + y
0 0 0
0 1 1
1 0 1
1 1 1
Tabela 2.2. Tabela operacji sumy logicznej
x x
0 1
1 0
Tabela 2.3. Tabela operacji negacji
2.2. Definicja algebry Boole a i postulaty Huntingtona
Przedstawimy poniżej podstawowe postulaty sformułowane przez Huntingtona.
Domknięcie względem operatora + i operatora "
Zbiór S jest domknięty ze względu na operator binarny, jeśli dla każdej pary elementów z tego
zbioru dany operator określa regułę na podstawie której otrzymamy żądany element w sposób
jednoznaczny z danego zbioru S. Aby dobrze zrozumieć regułę domknięcia wystarczy przeana-
lizować prosty przykład. Dany jest zbiór S, który jest zbiorem liczb naturalnych = {1, 2, 3, . . .}.
Zbiór ten jest domknięty względem operatora binarnego (+), ponieważ dla każdej pary elemen-
tów a, b " N otrzymujemy w sposób jednoznaczny c " Na + b = c. Natomiast dany zbiór S nie
jest domknięty względem operatora binarnego minus (-), gdyż wynik działania tego operatora
nie należy do zbioru liczby naturalnych np.: 3 - 4 = -1, a, b " N lecz c " N.
Element identycznościowy względem + i " .
Dla  + oznaczamy jako  0 ponieważ: x + 0 = 0 + x = x, dla  "  oznaczamy jako  1
ponieważ x � 1 = 1 � x = x. Zbiór S posiada element identycznościowy względem operacji
" , jeśli istnieje element e tego zbioru taki, że po wykonaniu danej operacji binarnej e � x =
x � e = x wartość elementu nie ulegnie zmianie, przy czym x również należy do zbioru S.
Analizując powyższe wyrażenie element e równy jest 1. Natomiast element  0 jest elementem
identycznościowym względem operacji  + wykonywanej na zbiorze liczb całkowitych C =
{... - 3, -2, -1, 0, 1, 2, 3, � � � } ponieważ: x + 0 = 0 + x = x, x należy do tego zbioru. Element
identycznościowy dla iloczynu to element multiplikatywny, natomiast dla sumy jest to element
addytywny.
Przemienność
Przemienność względem dodawania: x + y = y + x oraz względem mnożenia: x � y = y � x.
Mówimy, że operator binarny " na zbiorze S jest przemienny, gdy zachodzi równość: x � y = y � x
dla każdego x, y " S. Przemienność wynika z symetrii tablic obu operatorów binarnych.
Rozdzielność
Rozdzielność mnożenia względem dodawania: x � (y + z) = (x � y) + (x � z) oraz rozdzielność
dodawania względem mnożenia: x + (y � z) = (x + y) � (x + z). Jeśli  � i  + są operatorami
binarnymi na zbiorze S, mówimy, że operator  � jest rozdzielny względem operatora  + wtedy,
gdy spełniona jest następująca równość:
x � (y + z) = (x � y) + (x � z)
2.2. Definicja algebry Boole a i postulaty Huntingtona 27
Rozdzielność mnożenia względem dodawania oraz dodawania względem mnożenia można
udowodnić na podstawie tabeli prawdy. Na podstawie tabeli dopełnień łatwo znajdujemy:
x + x = 1, stąd 0 + 0 = 0 + 1 = 1 oraz 1 + 1 = 1 + 0 = 1
x � x = 0, stąd 0 � 0 = 0 � 1 = 0 oraz 1 � 1 = 1 � 0 = 0
X(Y + Z) = (X � Y ) + (X � Z)
X Y Z Y + Z X(Y + Z) X � Y X � Z X � Y + X � Z =
0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 1
0 1 0 1 0 0 0 0 1
0 1 1 1 0 0 0 0 1
1 0 0 0 0 0 0 0 1
1 0 1 1 1 0 1 1 1
1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1
Tabela 2.4. Tabela prawdy dla rozdzielności mnożenia względem dodawania.
X + (Y � Z) = (X + Y ) � (X + Z)
X Y Z Y � Z X + (Y � Z) X + Y X + Z (X + Y ) � (X + Z) =
0 0 0 0 0 0 0 0 1
0 0 1 0 0 0 1 0 1
0 1 0 0 0 1 0 0 1
0 1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1 1
1 0 1 0 1 1 1 1 1
1 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1
Tabela 2.5. Tabela prawdy dla rozdzielności dodawania względem mnożenia.
Prawo łączności
Mówimy, że operator binarny  "  na zbiorze S jest łączny wtedy gdy jest spełniony następujący
warunek:
(x � y) � z = x � (y � z) dla każdego x, y, z " S
.
Dopełnienie zbioru
Dla każdego elementu x " B istnieje taki element x " B, że x + x = 1 oraz x � x = 0. Jego
graficzną reprezentacją jest diagram Venna. Istnieją przynajmniej dwa elementy takie,
że: x, y " B, x = y. W tabeli 2.6 na stronie 28 zaprezentowane są postulaty Huntingtona 

postulaty te są ściśle związane z przedstawionymi powyżej definicjami algebry Boole a.
28 Rozdział 2. Logika binarna
Rysunek 2.1. Diagram Venna
  CZ
ŚĆ A CZ
ŚĆ B
POSTULAT 1 X, Y " B �! X + Y " B X, Y " B �! X � Y " B
POSTULAT 2 X + 0 = X X � 1 = X
POSTULAT 3
X + Y = Y + X X � Y = Y � X
PRZEMIENNOŚĆ
POSTULAT 4
X(Y + Z) = XY + XZ X + (Y � Z) = (X + Y ) � (X + Z)
ROZDZIELNOŚĆ
POSTULAT 5 X + X = 1 X � X = 0
Tabela 2.6. Tabela postulatów Huntingtona
Algebra Boole a oprócz definicji przedstawionych w niniejszym podrozdziale, zawiera też
twierdzenia, których dowody przedstawiamy poniżej.
Twierdzenie 1
x + x = x
x + x = x
x + x = x
Dowód tego twierdzenia przebiega następująco:
x + x = (x + x) � 1 post. 2b
= (x + x) � (x + x) post. 5a
= x + x � x post. 4b
= x + 0 post. 5b
= x post. 2a
x � x = x
x � x = x
x � x = x
2.2. Definicja algebry Boole a i postulaty Huntingtona 29
Dowód tego twierdzenia przebiega następująco:
x � x = (x � x) + 0 post. 2a
= (x � x) + (x � x) post. 5b
= x + x � x post. 4a
= x � 1 post. 5a
= x post. 2b
Twierdzenie 2
x + 1 = 1
x + 1 = 1
x + 1 = 1
Dowód tego twierdzenia przebiega następująco:
x + 1 = 1 � (x + 1) post. 2b
= (x + x) � (x + 1) post. 5a
= x + (x � 1) post. 4b
= (x + x) post. 2b
= 1 post. 5a
x � 0 = 0
x � 0 = 0
x � 0 = 0
Dowód tego twierdzenia przebiega następująco:
x � 0 = 0 + (x � 0) post. 2a
= (x � x) + (x � 0) post. 5b
= x � (x + 0) post. 4a
= x � x post. 2a
= 0 post. 5b
Twierdzenia de Morgana
 (x + y) = x � y
 (x � y) = x + y
(x + y) = x � y
(x + y) = x � y
(x + y) = x � y
Dowód tego twierdzenia przebiega następująco:
(x + y) = (x + y)(x + y)(x + y) wzór kanoniczny
(x + y) = (x + y)(x + y)(x + y) post. 3
= [(y + x)(y + x)](x + y) post. 4b
= [y(x + x)](x + y) post. 5a
= (y � 1)(x + y) post. 2b
= y(x + y) post. 4a
= y x + yy post. 5b
= y x + 0 post. 2a
= y x post. 3b
= x y
(x � y) = x + y
(x � y) = x + y
(x � y) = x + y
Dowód tego twierdzenia przebiega następująco:
(x � y) = (x y) + (xy) + (xy) wzór kanoniczny
(x � y) = (x y) + (xy) + (xy) Tw. 1a
= x y + xy + x y + xy post. 3b
= y x + yx + x y + xy post. 4a
= y(x + x) + x(y + y) post. 5a
= y � 1 + x � 1 post. 2b
= y + x post. 3a
= x + y
30 Rozdział 2. Logika binarna
Postać kanoniczna
Zwana jest również postacią alternatywowo-koniunkcyjną. Jest to postać, która przedstawia
dane twierdzenie za pomocą sumy atomów. Ponieważ atomy te odpowiadają iloczynom mini-
malnym, każde wyrażenie boolowskie zawierające n zmiennych jest równoważne z sumą różnych
iloczynów minimalnych. Takie przedstawienie w postaci sumy jest jednoznaczne, z dokładnością
do porządku jakim są wypisywane te iloczyny minimalne[3].
Twierdzenie o absorpcji
Istnieją przynajmniej dwa elementy x, y " B, takie, że x + xy = x.
x + xy = x
x + xy = x
x + xy = x
Dowód tego twierdzenia przebiega następująco:
x + xy = x � 1 + xy post. 2b
= x � (1 + y) post. 3a
= x � (y + 1) Tw. 2a
= x � 1 post. 2b
= x
Własności algebry Boole a zaprezentowane podsumowuje następująca definicja oraz niżej
zaprezentowana tabela.
Dualizm
Dualizm algebry Boole a jest właśnością, która mówi, że każde wyrażenie algebraiczne, które
da się wyprowadzić na podstawie postulatów algebry Boole a pozostaje słuszne, jeśli operatory
i elementy identycznościowe zostaną zamienione. Np.: 0 na 1 i operator I na LUB.
2.3. Funkcje boolowskie
Funkcje boolowskie są to wyrażenia utworzone przy pomocy zmiennych binarnych oraz dwóch
operatorów binarnych: I oraz LUB, jednego operatora unarnego NIE, nawiasów oraz znaku
równości. Funkcja boolowska przyjmuje wartości: 0 lub 1 dla zadanych zmiennych. Na przykład:
Wez
my funkcję: F = xyz Funkcja F równa jest 1 jeśli x = 1, y = 1, z = 0, w innych przypadkach
F = 0.
Każda funkcja boolowska może być przedstawiona za pomocą tablicy prawdy. Liczba wierszy
w tej tablicy dana jest wzorem i wynosi 2n, gdzie n jest liczbą zmiennych. Ciągi zer i jedynek
występujące w każdym wierszu tej tabeli można otrzymać biorąc kolejne liczby binarne od 0
do 2n - 1. Każdej z nich odpowiada przy tym wartość funkcji wynosząca 1 lub 0. Funkcje są
tworzone poprzez połączenie dwóch lub więcej zmiennych przy pomocy operatorów binarnych
n
I oraz LUB. Funkcje te wyglądają następująco: x � y oraz x + y. Dowiedziono iż istnieje 22
funkcji n zmiennych. Dla dwóch zmiennych x i y istnieje 16 możliwych do utworzenia funkcji.
Tabela funkcji boole owskich dla dwóch zmiennych x, y jest następująca:
2.3. Funkcje boolowskie 31
  CZ
ŚĆ A CZ
ŚĆ B
POSTULAT 2 X + 0 = X X � 1 = X
POSTULAT 5 X + X = 1 X � X = 0
TWIERDZENIE 1 X + X = X X � X = X
TWIERDZENIE 2 X + 1 = 1 X � 0 = 0
TWIERDZENIE 3
(X) = X
INWOLUCJA
POSTULAT 3
X + Y = Y + X X � Y = Y � X
PRZEMIENNOŚĆ
TWIERDZENIE 4
X + (Y + Z) = (X + Y ) + Z X � (Y � Z) = (X � Y ) � Z
A

CZNOŚĆ
POSTULAT 4
X(Y + Z) = XY + XZ X + (Y � Z) = (X + Y )(X + Z)
ROZDZIELNOŚĆ
TWIERDZENIE 5
(X + Y ) = X � Y (X � Y ) = X + Y
de MORGANA
TWIERDZENIE 6
X + XY = X X(X + Y ) = X
ABSORPCJA
Tabela 2.7. Zestawienie twierdzeń algebry Boole a i postulatów Huntingtona
X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
I / / �" + �! �! Ź �! Ź �! ę!
Tabela 2.8. Tablica funkcji boolowskich
Legenda:
/  zakaz
�"  albo
+  lub
�!  nor
�!  równoważność
Ź  negacja
�!  implikacja
�!  implikacja
ę!  nand
32 Rozdział 2. Logika binarna
F0 = 0 0
F1 = x � y I
F2 = x � y = x / y zakaz (x, nie y)
F3 = x x
F4 = x � y = y / x zakaz (y, nie x)
F5 = y y
F6 = x � y + x � y = x �" y albo
F7 = x + y lub
F8 = (x + y) = x �! y nie lub
F9 = x � y + x � y = x �! y równoważność
F10 = y nie y
F11 = x + y = x �! y Implikacja (x, nie y)
F12 = x nie x
F13 = x + y = x �! y Implikacja (y, nie x)
F14 = (x � y) = x ę! y NAND (nie i)
F15 = 1 1
Dowód dla funkcji boolowskich - relacja F6 do F9:
F6 = x � y + x � y = x �" y albo
F9 = x � y + x � y = x �! y równoważność
F6 = xy + xy Tw. 3
= ((xy + xy)) Prawa de Morgana
= ((xy) (xy) Prawa de Morgana
= ((x + y)(x + y)) post. 4
= (xx + xy + x y + yy) post. 2
= (xy + x y)
= F9
2.3. Funkcje boolowskie 33
Przykład 16. Minimalizacja funkcji drogą przekształceń formalnych:
f = a � b � c � a � c � b � d � c � d
Minimalizując funkcję korzystamy z twierdzeń i postulatów ujętych w tabeli 2.7 na
stronie 31
f = a � b � c � a � c � b � d � c � d Prawa de Morgana
= a � b � c � a � c � b � d � (c + d) Prawa de Morgana
= a � b � c � a � c � (b + d + c � d) post. 4
= a � b � c � a � c � (b + d(1 + c) Tw. 6 absorpcja
= a � b � c � a � c � (b + d Tw. 2
= a � b � c � a + c + b � d Prawa de Morgana
= a � (b + c + (ac(b + d))) post. 4
= a � (b + c + acb + acd) Tw. 6 absorpcja
= a � (b + c + acd) Prawa de Morgana
= a + bc(a + c + d) post. 4
= a + abc + bcc + bcd Tw. 6 absorpcja
= a + bcc + bcd post. 5
= a + bcd post. 5
Przykład 17. Minimalizacja funkcji drogą przekształceń formalnych.
f = a � b + c + a � b � c + a + b + c + a + b + c
= (a + b) � c + (a + b) � c + a � b � c + a � b + c
= (a + b) � c + (a + b) � c + a � b � c + a � b + c
= (a + b)(c + c) + ab(c + 1) + c
= a + b + ab + c
= a(1 + b) + b + c
= a + b + c
Rozdział 3
Translacja wyrażeń arytmetycznych
Głównym tematem tego rozdziału jest proces translacji i wszystkie pojęcia z tym procesem
związane. Ponadto w tym rozdziale zostaną przedstawione wszystkie algorytmy wykorzystywane
do translacji wrażeń arytmetycznych, takie jak: algorytm translacji wyrażeń na ONP, algorytm
przejścia z postaci postfiksowej na postać infiksową, algorytm konwersji wyrażeń z instrukcją
warunkową oraz algorytm translacji wyrażeń zapisanych w ONP na wyrażenia zapisane w języku
symbolicznym. Wszystkie te algorytmy poparte zostaną przykładami.
3.1. Podstawowe informacje o translacji i translatorach
Instrukcje programu zapisane w wybranym języku programowania muszą być zrozumiałe dla
mikroprocesora komputera dlatego muszą być modyfikowane. Taki proces to translacja  polega
na przetłumaczeniu tekstów zapisanych w jednym języku na inny, zrozumiały przez maszynę cy-
frową. Translatory mają za zadanie, przetwarzać algorytmy zapisane w językach programowania
niskiego i wysokiego poziomu na język, dzięki któremu komputer wykona szereg efektywnych
instrukcji zapisanych przez programistę[1].
Translatory możemy podzieli na dwie kategorie: kompilatory i interpretery: kompilator ope-
ruje na całym tekście programu z
ródłowego i generuje program jak całość. Zatem do wykona-
nia programu możemy przystąpić dopiero po jego kompilacji. Interpreter natomiast, operuje
na poszczególnych fragmentach programu z
ródłowego  jednostkach syntaktycznych i generuje
fragmenty programu  przekłady tych jednostek. Używając interpretera możemy wykonywać
poszczególne części programu nie czekając na translację całego programu[1].
Jednak sytuacją najczęściej spotykaną jest wprowadzony proces pośredni, to znaczy język ze-
wnętrzny w pierwszym etapie tłumaczenia zostaje przełożony na język asemblerowy, natomiast
w kolejnym etapie następuje translacja języka asemblerowego na język symboliczny[1].
Stos  jest to organizacja sekwencyjna pamięci operacyjnej maszyny cyfrowej. Ze stosu
w jednym kroku możemy pobrać tylko jeden element. Organizacja stosu LIFO  last in first
out (z ang.), czyli element ostatni zostaje odłożony na stosie, a pierwszy zostaje z niego zdjęty.
Elementy odkładane są na stosie, ale dostępny jest tylko element znajdujący się na szczycie.
Kolejka to również organizacja pamięci, FIFO  first in first out (z ang.), czyli element
zostaje dołożony do kolejki jako pierwszy i pierwszy z niej zostanie zdjęty.
Odwrotna Notacja Polska(ONP), czyli beznawiasowa symbolika logiczna. Jest to system
beznawiasowego przedstawiania wyrażeń formalnych. W zapisie takim symbole zmiennych po-
przedzają bezpośrednio symbole operacji, czyli jest to notacja postfiksowa. Twórcą tej metody
jest polski logik Jan A
ukasiewicz (1878  1956).
Możemy wyróżnić trzy rodzaje notacji:
 infiksową: a + b,
 prefiksową: +ab,
 postfiksową: ab+.
36 Rozdział 3. Translacja wyrażeń arytmetycznych
Rysunek 3.1. Schemat tworzenia programu
Rysunek 3.2. Model automatu ze stosem do translacji wyrażeń arytmetycznych
3.2. Algorytm translacji wyrażeń na ONP
Algorytm translacji wyrażeń na ONP (algorytm Władysława Turskiego) [1].
Algorytm ten można przedstawić w następujących punktach:
1. Pobierz kolejny element, który może być nazwą zmiennej, stałą lub ogranicznikiem z
ródło-
wego wyrażenia.
2. Jeżeli ten element jest nazwą zmiennej lub stałą przekaż go natychmiast na wyjście au-
tomatu. W przeciwnym wypadku, jeśli priorytet ogranicznika jest wyższy od priorytetu
zajmującego szczyt stosu lub jeśli stos jest pusty, wówczas dopisz go na stos.
3. Jeśli na szczycie stosu znajduje się ogranicznik o priorytecie równym lub wyższym od aktu-
alnie pobieranego elementu, odczytaj go ze stosu i prześlij na wyjście, natomiast ogranicznik
z wejścia dopisz na stos, chyba że nowy ogranicznik zajmujący szczyt stosu w wyniku od-
czytania ma priorytet nie mniejszy niż ogranicznik z wejścia. W takim wypadku należy
kontynuować odczytywanie elementów ze stosu i przesyłanie ich na wyjście, aż do wystą-
pienia na szczycie stosu ogranicznika o priorytecie niewyższym od priorytetu ogranicznika
pochodzącego z wejścia.
4. Jeśli wyrażenie z
ródłowe zostało wyczerpane, należy odczytać wszystkie ograniczniki ze stosu
aż do wyczerpania automatu.
3.2. Algorytm translacji wyrażeń na ONP 37
OGRANICZNIK PRIORYTET
( 0
+ - ) 1
" / � 2
"
Ć 3
sin cos tg ctg NEG 4
Tabela 3.1. Tabela ograniczników i priorytetów
Priorytety ograniczników:
Działanie automatu należy uzupełnić regułami. Ogranicznik  ( jest dopisywany na stos bez
jakiegokolwiek odczytywania ze stosu, natomiast ogranicznik  ) nie jest dopisywany na stos,
ponieważ pojawienie się go na wejściu powoduje odczytanie ze stosu i przesłanie na wyjście
wszystkich kolejnych ograniczników o priorytecie niemniejszym niż 1. Ogranicznik  ( ze szczy-
tu stosu zostaje usunięty bez przekazywania na wyjście, jeśli aktualnym symbolem na wejściu
jest  ) . Pozostałe elementy przesuwają się o jedno miejsce. Pojawienia się  ) na wejściu au-
tomatu powoduje wprowadzenie na wyjście wszystkich ograniczników z wnętrza pary nawiasów
aż do  ( oraz likwidację tego nawiasu. Stosując powyższy algorytm oraz tabelę ograniczników
i reguły jej towarzyszące prezentujemy przykłady translacji wyrażeń na ONP.
Przykład 18. Poniższe wyrażenie zapisz w ONP:
W = a + b � 3 - z2
TAKT WEJŚCIE STOS WYJŚCIE
1 a a
2 + +
3 b b
4 " +,"
5 3 +," 3
6   "
 +
7 z  z
8 Ć  ,Ć
9 2  ,Ć 2
10 ; Ć

W = a b 3 " + z 2 Ć -
Przykład 19. Poniższe wyrażenie zapisz w ONP:
W = 3(a + 5b) - 3x2
38 Rozdział 3. Translacja wyrażeń arytmetycznych
TAKT WEJŚCIE STOS WYJŚCIE
1 3 3
2 " "
3 ( " ,(
4 a " ,( a
5 + " ,(,+
6 5 " ,(,+ 5
7 " " ,(,+,"
8 b " ,(,+," b
9 ) " "
+
10   "
11 3  3
12 "  ,"
13 x  ," x
14 Ć  ," ,Ć
15 2  ," ,Ć 2
16 ; Ć
"

W = 2 a 5 b " + " 3 x 2 Ć " -
3.3. Algorytm przejścia z postaci postfiksowej na postać infiksową
Algorytm przejści przejścia z postaci postfiksowej na postać infiksową:
1. Odczytujemy kolejne znaki wyrażenia w postaci postfiksowej (od lewej do prawej) i szukamy
pierwszego symbolu operacji,
2. Jeśli jest to operacja binarna, wtedy łączymy nią dwie pierwsze zmienne lub wyrażenia leżące
na lewo od symbolu tej operacji,
3. Jeśli jest to operacja unarna, łączymy z nią pierwszą leżącą na lewo od symbolu zmienną
lub wyrażenie,
4. Jeśli nie był to ostatni symbol operacji powtarzamy krok 1 i 2 tworząc tzw. dendrogram,
dopóki nie wykorzystamy wszystkich znaków operacji.
Rysunek 3.3. Schemat dla przykładu przejścia z postaci postfiksowej na infiksową
3.4. Algorytm konwersji z instrukcją warunkową 39
PRIORYTET PRIORYTET
OGRANICZNIK
STOSOWY PORÓWNAWCZY
(, if 0 
then 0 1
else 1 2
), ;  1
a" 3 3
�" 4 4
(" 5 5
'" 6 6
 7 7
<, >, , , =, = 8 8

+,  9 9
" , /, NEG 10 10
"
Ć, 11 11
Tabela 3.2. Tabela priorytetów ograniczników z elementami logicznymi
3.4. Algorytm konwersji z instrukcją warunkową
Rysunek 3.4. Schemat blokowy instrukcji if-then-else
Instrukcja if-then-else powoduje konieczność wprowadzenia dwóch priorytetów: skoku wa-
runkowego i skoku bezwarunkowego, należy również wprowadzić numerację dotyczącą wyprowa-
dzenia kolejnych elementów w ONP. Skoki warunkowe występujące w ONP oznaczają, że jeśli
wyrażenie logiczne poprzedza wystąpienie skoku warunkowego ma wartość false to elementy
ONP tego wyrażenia, w którym wystąpił skok warunkowy powinny być pominięte aż do k - 1
elementu.
Analogicznie wystąpienie skoku bezwarunkowego oznacza, że elementy ONP między sko-
kiem bezwarunkowym i k-tym elementem mogą być pominięte. Poniżej przedstawiamy tabele
priorytetów ograniczników wraz z elementami logicznymi:
Algorytm konwersji wyrażeń z instrukcją warunkową:
1. Gdy na wejściu pojawi się ogranicznik then, oprócz wszystkich ograniczników przepisy-
wanych ze stosu na wyjście ze względu na ich priorytety, także zostaje usunięty ze stosu
ogranicznik if. Do ONP zaś wpisana zostaje operacja skoku warunkowego z pustym nawia-
40 Rozdział 3. Translacja wyrażeń arytmetycznych
sem, then natomiast zostaje dopisany na stos z numerem, pod jakim występuje w ONP
operacja skoku warunkowego.
2. Gdy na wejściu pojawi się ogranicznik else powoduje on odczytanie zawartości stosu, aż do
then (możliwość kontroli skoku), który zapisywany jest wraz z numerem, pod którym wy-
stępuje stowarzyszony skok warunkowy SW. Do ONP dopisywany jest skok bezwarunkowy
z pustym nawiasem, a operacja skoku warunkowego zostaje uzupełniona przez wpisanie do
nawiasu bieżącego numeru pozycyjnego w produkowanym zapisie ONP. Ogranicznik else
zostaje dopisany na stos wraz z numerem pozycyjnym skoku bezwarunkowego SB:
if then - SW( )  w nawiasie znajduje się numer pozycyjny skoku warunkowego
w nawiasie znajduje się bieżący numer produkowanego zapisu
else - SB( ) 
w ONP (następny wolny)
3. W chwili, gdy odczytywanie ze stosu produkuje else zostaje uzupełniona odpowiadająca
operacja SB bieżącym numerem produkowanego zapisu ONP.
W przykładach dotyczących algorytmu z instrukcją warunkową if-then-else, górne indeksy
przy then i else oznaczają numer pozycyjny instrukcji SW i SB w ONP, zaś indeksy dolne
oznaczają priorytet stosowy lub porównawczy danego ogranicznika.
Poniżej przedstawiamy przykład translacji wyrażeń na ONP według algorytmu z instrukcją
warunkową:
Przykład 20. Podane wyrażenie przedstaw w ONP za pomocą algorytmu z instrukcją warun-
kową ONP:
W = if x > 0 then y/x else y/(x + l)
Przykład znajduje się na stronie 40 w tabeli 3.3.
TAKT WEJŚCIE STOS WYJŚCIE NR POZYCYJNY
1 if if0
2 x if0 x 1
3 >8 if0,>8
4 0 if0,>8 0 2
5 then1 then0 > 3
SW(9) 4
6 y then4 y 5
0
7 /10 then4,/10
0
8 x then4,/10 x 6
0
9 else2 else8 7
1
SB(14) 8
10 y else8 y 9
1
11 /10 else8,/10
1
12 ( else8,/10,(0
1
13 x else8,/10,(0 x 10
1
14 +9 else8,/10,(0,+9
1
15 1 else8,/10,(0,+9 1 11
1
16 ) else8,/10 + 12
1
17 ; / 13
Tabela 3.3. Przykład algotyrmu z konwersją wyrażeń z instrukcją warunkową
3.5. Algorytm translacji zapisu ONP na język symboliczny 41
3.5. Algorytm translacji zapisu ONP na język symboliczny
Algorytm translacji zapisu ONP na język symboliczny:
1. Ustalamy, że i = 0, k = 1,
2. Odczytujemy k-ty element ONP: �k
3. Jeżeli �k jest nazwą zmiennej lub stałą, generujemy operację w postaci Ii = �k i następnie
zwiększamy i o 1 (i = i + 1).
4. Jeśli �k jest symbolem operacji binarnej generujemy Ii-2 = Ii-2 opII Ii-1. Jeśli �k jest
symbolem operacji unarnej wówczas generuje się instrukcję Ii-1 = opI Ii-1
5. Jeśli �k nie był ostatnim symbolem wyrażenia w ONP to zwiększamy k o 1 (k = k + 1)
i przechodzimy do punktu 2.
Poniżej przedstawiamy przykład translacji zapisu ONP na język symboliczny:
Przykład 21. Poniższe wyrażenie ONP zapisz w języku symbolicznym:
W = a b - 1 2 / Ć 7 - x 2 Ć x 2 + a b + Ć - /
Przykład znajduje się na stronie 41 w tabeli 3.4
I0:=a k=1 i=0
I1:=b k=2 i=1
I0:=I0-I1 k=3 i=2
I1:=1 k=4 i=1
I2:=2 k=5 i=2
I1:=I1/I2 k=6 i=3
I0:=I0ĆI1 k=7 i=2
I1:=7 k=8 i=1
I0:=I0-I1 k=9 i=2
I1:=x k=10 i=1
I2:=2 k=11 i=2
I1:=I1ĆI2 k=12 i=3
I2:=x k=13 i=2
I3:=2 k=14 i=3
I2:=I2+J3 k=15 i=4
I3:=a k=16 i=3
I4:=b k=17 i=4
I3:=I3+I4 k=18 i=5
I2:=I2�1 k=19 i=4
I1:=I1-I2 k=20 i=3
I0:=I0/I1 k=21 i=2
Tabela 3.4. Przykład przejścia z ONP na język symboliczny
Rozdział 4
Maszyna Turinga i automaty skończone
Tematyką tego rozdziału będzie podstawowy model maszyny Turinga jego budowa oraz pojęcia
z tym modelem związane. Zostaną również zaprezentowane problemy, w rozwiązywaniu których
znalazła zastosowanie maszyna Turinga. W rozdziale tym zostanie również przedstawiona te-
matyka związana z automatami skończonymi. Pokazane będą trzy rodzaje automatów skończo-
nych: niederministyczny automat skończony, deterministyczny automat skończony oraz automat
z �-ruchami. Wszystkie rodzaje automatów zilustrujemy za pomocą przykładów. Rozdział ten
obejmuje również teorię związaną z wyrażeniami regularnymi oraz konstruktorami.
4.1. Maszyna Turinga
Maszyna Turinga jest modelem matematycznym komputera. Została wymyślona przez Alana
Turinga  brytyjskiego matematyka[4]. Podstawowy model przedstawiony na poniższym ry-
sunku składa się z następujących elementów:
 skończonego alfabetu symboli,
 skończonego zbioru stanów,
 nieskończonej taśmy z zaznaczonymi polami (w kształcie kwadratu), z których każde może
zawierać pojedynczy element,
 ruchomej głowicy odczytująco-zapisującej, która może poruszać się wzdłuż taśmy przesuwa-
jąc się na raz o jedno pole, głowica w danej chwili widzi tylko jedną stronę taśmy,
 diagram przejść między stanami (nazywanym również diagramem przejść lub tabelą stanów),
który zawiera instrukcję powodującą zmiany.
Rysunek 4.1. Podstawowy model Maszyny Turinga
Ciąg symboli wejściowych wpisywany jest na taśmę począwszy od lewej strony. Reszta wolnych
pól wypełniana jest specjalnym symbolem taśmowym nazywanym symbolem pustym. Maszyna
Turinga w pojedynczym ruchu może:
 zmienić stan,
 wpisać symbol w obserwowanej komórce taśmy, zastępując symbol tam wpisany,
 przesunąć głowicę o jedną komórkę w prawo lub w lewo.
Poniżej chcielibyśmy zaprezentować formalny zapis Maszyny Turinga [5].
MT = < Q, Ł, �, �, q0, B, F >
MT = < Q, Ł, �, �, q0, B, F >
MT = < Q, Ł, �, �, q0, B,F >,
gdzie:
Q
Q  skończony zbiorem stanów,
Q
44 Rozdział 4. Maszyna Turinga i automaty skończone
�
�  skończony zbiór dopuszczalnych symboli taśmowych,
�
B �
B  symbol pusty należący do �
B �,
Ł � B
Ł  podzbiór � nie zawierający B zwany zbiorem symboli wejściowych,
Ł � B,
�
�  funkcja następnego ruchu, będąca odwzorowaniem Q � � - Q � � � {L, P, -}
�
gdzie:
L
L  oznacza ruch w lewo,
L
P
P  ruch w prawo,
P
q0
q0  stan początkowy,
q0
F ą" Q
F ą" Q  zbiór stanów końcowych.
F ą" Q
Przy każdym odczycie ze zbioru stanu mamy do czynienia z ruchem głowicy. Ruch na taśmie
powoduje zmianę stanu, która jest uaktualniana w liczniku wielokrotności zapisu na taśmie.
Czas zapisywania danej wartość na taśmie to sekwencja następujących po sobie stanów. Dzia-
łanie maszyny Turinga można przedstawić na dwa sposoby. Pierwszy sposób to przedstawienie
w postaci diagramu przejść stanów, drugi natomiast to tabela stanów. Oba te sposoby zostaną
omówione poniżej.
Diagram przejść stanów  jest to graf skierowany, którego wierzchołki reprezentują sta-
ny. Przejściem natomiast będziemy nazywać krawędz
łączącą dwa stany s i t. Każdą krawędz

będziemy etykietować kodem postaci (a  b, kierunek), gdzie a i b są symbolami, a kierunek
to przesunięcie w lewo bądz
w prawo. Część a etykiety jest nazywana wyzwalaczem przejścia,
a część b Ąb, kierunekż nazywana jest akcją. W czasie swego działania maszyna Turinga, kiedy
tylko przejdzie do stanu s, a symbolem odczytanym przez głowicę będzie a, to w to miejsce a
zostanie wpisany symbol b, głowica natomiast wykona przesunięcie o jedno pole w kierunku do
stanu t.
Rysunek 4.2. Graf przejść między stanami
Tabela stanów  również określa przejścia między stanami dla maszyny Turinga. Tabela
ta zawiera wszystkie symbole alfabetu wejściowego jak również wszystkie stany, w których może
znalez
ć się maszyna Turinga. W każdym polu tabeli stanów określamy:
 dla danego stanu qi kolejny stan qi+1,
 symbol, który ma być zapisany na taśmie,
 kierunek (w lewo bądz
w prawo) ruchu głowicy.
Dla obu sposobów zapisu stanów maszyny Turinga możemy wyróżnić specyficzne stany: stan
początkowy, jeden lub kilka stanów końcowych często nazywanymi stanami biernymi. Maszyna
rozpoczyna swoje działanie od stanu początkowego, jest to pierwsze niepuste pole od lewej
strony i porusza się krok po kroku zgodnie z wcześniej narzuconym ruchem, natomiast koniec
działania maszyny Turinga następuje wtedy, kiedy jej głowica napotka stan końcowy.
4.1. Maszyna Turinga 45
Przykład 22. Podwajanie symboli w słowie.
Poniżej przedstawiamy przykład algorytmu dla maszyny Turinga, która podwaja symbole w sło-
wie:
Ł = {a, b} � = {Ć, a, b}
Zatem, na przykład podając słowo ab, w efekcie działania maszyny Turinga otrzymamy
słowo aabb, natomiast podając słowo wejściowe aba na wyjściu otrzymamy słowo aabbaa. Słowo
zapiszemy na taśmie w następujący sposób: ĆĆĆabĆĆĆ
Pierwszym krokiem jest wypisanie wszystkich symboli � = {Ć, a, b} oraz stanu początkowego
q0. Kolejnym krokiem jest sprawdzenie stanu q0 tzn. jaki symbol został odczytany w stanie q0.
Jeśli jest to Ć to nie zmieniamy stanu tylko przesuwamy głowicę o jedno pole w prawo (rys.
4.3). Natomiast, jeśli w q0 odczytamy symbol a, to wówczas należy wpisać w jego miejsce Ć
(oznaczające jego pobranie) i przejść w prawo do stanu q1 (rys. 4.4).
Następnie znajdując się w stanie q1 należy przesuwać się w prawo, aż pominiemy wszystkie
symbole wraz z pierwszym na taśmie symbolem Ć. Wówczas w miejsce drugiego Ć na taśmie
wpisujemy a i zmieniamy stan na q3. Kolejnym napotkanym symbolem w stanie q3 jest symbol
Ć, gdzie zapisujemy kolejne a i zmieniamy stan na q4  jest to stan powrotu.
Znajdując się w tym stanie musimy jeszcze przejść nad wszystkimi symbolami i jeśli napo-
tkamy symbol Ć, sprawdzamy, czy na taśmie wyczerpały się symbole wejściowe. Jeśli istnieją
jeszcze jakieś symbole na taśmie, to wówczas należy rozpocząć działanie algorytm od początku,
w przeciwnym razie należy przejść do stanu końcowego q15 (stanu biernego).
Oczywiście powyższy algorytm stosujemy dla wszystkich znaków alfabetu wejściowego.
Rysunek 4.3. Fragment tabeli przejść dla po- Rysunek 4.4. Fragment tabeli przejść dla po-
wyższego przykładu wyższego przykładu
Zatem kompletna tabela przejść będzie się prezentowała w sposób następujący:

Q

q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 q12 q13
Ł


q0 q2 q3 q4 q5 q13 q0 q8 q9 q10 q11 q13 q0
Ć SB
Ć, P Ć, P a, P a, L Ć, L Ć, P Ć, P Ć, P b, P b, L Ć, L Ć, P Ć, P
q1 q1 q2 q13 q4 q6 q6 q7 q8 q13 q10 q12 q12
a SB
Ć, P a, P a, P a, P a, L a, L a, L a, P a, P a, P a, L a, L a, L
q7 q1 q2 q13 q4 q6 q6 q7 q8 q13 q10 q12 q12
b SB
Ć, P b, P b, P b, P b, L b, L b, L b, P b, P b, P b, L b, L b, L
Tabela 4.1. Tabela stanów maszyny Turinga podwajająca symbole w słowie dla alfabetu wejściowego
Ł = {a, b}
Przykład 23. Odejmowanie binarne:
Dla alfabetu Ł = {1, -, +, 0, =}, należy skonstruować tablicę przejść stanów dla maszyny Tu-
46 Rozdział 4. Maszyna Turinga i automaty skończone
WE: 11111 - 111 = WY: +11
WE: 111 - 111 = WY: 0
WE: 111 - 11111 = WY: -11
Tabela 4.2. Tabela wyrażeń dla rezalizowanego przykładu maszyny Turinga.
ringa, której zadaniem będzie realizacja operacji odejmowania. Przykładowe wyrażenia są nastę-
pujące:
Poniżej prezentujemy algorytm słowny realizujący tabelę przejść stanów dla przykładu, do-
datkowo przyjmujemy założenie, iż zaczynamy od prawej strony słowa wejściowego i operujemy
tylko na słowie wejściowym. Algorytm możemy przedstawić w następujących punktach:
1. Pobieramy symbol, wymazując go.
2. Jeżeli odczytany symbol to  1 , idziemy w lewo omijając wszelkie symbole do pierwszego
symbolu słowa wejściowego, a następnie wymazujemy ten symbol. Przesuwamy się w prawo
do kolejnego symbolu:
 Jeżeli kolejnym symbolem jest  1 to omijamy go, omijamy również wszystkie kolejne
symbole, idąc w prawo do ostatniego symbolu słowa wejściowego następnie przechodzimy
do punktu nr 1.
 Jeżeli natomiast kolejnym symbolem jest  - to omijamy go idąc w prawo i jeżeli kolejnym
symbolem jest  1 to kończymy prace algorytmu.
 Jeżeli kolejnym symbolem jest miejsce puste to zamiast  - wpisujemy  0 ; wówczas
również kończymy prace algorytmu.
3. Jeżeli odczytany symbol to  - , przesuwamy się w lewo omijając wszystkie jedynki, wówczas
w pierwsze wolne miejsce wpisujemy  + i kończymy prace algorytmu.
W przykładzie tym definiujemy Maszynę Turinga jako:
MT = < Q, Ł, �, �, q0, B, F >
MT = < Q, Ł, �, �,q0, B, F >
MT = < Q,Ł, �,�, q0,B, F >
gdzie:
Q
Q = {q0 � � � q7},
Q
�
� = {Ć, 1, -, =}
�
�
� = Q � � - Q � � � {L, P, -}
�
B
B = {Ć},
B
q0
q0 = {q0}
q0
F
F = {SB}
F
Dla powyższego algorytmu możemy przedstawić następującą tabelę przejść stanów:
Zatem przykładowe wyrażenie wraz z poszczególnymi etapami przejścia przez maszynę Tu-
ringa będzie wyglądać tak:
111 - 1 =�! 111 - Ć =�! Ć11 - Ć =�! Ć11ĆĆ =�! +11ĆĆ
Alternatywą dla tabeli przejść między stanami maszyny Turinga jest graf przejść stanów.
Poniżej przedstawiamy przykład realizowany właśnie za pomocą grafu przejść stanów.
Przykład 24. Inkrementacja liczb binarnych:
Maszyna Turinga dodająca 1 do danej liczby zapisanej w systemie dwójkowym. Jedynka ta dopi-
sywana jest do liczby bez znaku. Zakładamy, że głowica na początku jest ustawiona na pierwszej
pozycji z prawej strony. Rozwiązanie zostało pokazana na stronie 47 (tabela oraz graf nr 4.1).
4.1. Maszyna Turinga 47

Q

q0 q1 q2 q3 q4 q5 q6 q7
Ł


q0 q2 q0 SB q6
Ć SB SB SB
Ć, L Ć, P Ć, L +, - Ć, L
q1 q1 q3 q4 q4 q5
1 SB SB
Ć, L 1, L Ć, P 1, P 1, P 1, L
q5 q1 q6 q4 q7 SB
- SB SB
Ć, L -, L -,P -,P -,- 0,-
q0
= SB SB SB SB SB SB SB
Ć, L
Tabela 4.3. Tabela stanów maszyny Turinga realizując operację odejmowania dla alfabetu wejściowego
Ł = {1, -, +, 0, =}

Q

q0 q1 q2
Ł


q0
Ć SB SB
Ć, L
q2 q2
0 SB
1, L 1, L
q1 q1
1 SB
0, L 0, L
Rysunek 4.5. Tabela stanów oraz graf przejść maszyny Turinga dodającej 1 do liczby binarnej
Maszyny Turinga pokazane w powyższych przykładach rozwiązywały problemy arytmetycz-
ne, które są związane z manipulacją danymi wejściowymi. Maszyny Turinga są stosowane rów-
nież do rozwiązywania problemów decyzyjnych. Przykład takiego zastosowania Maszyny Turin-
ga zostanie pokazany poniżej.
Przykład 25. Sprawdzenie czy podane słowo jest palindromem
Maszyna Turinga bada, czy dane słowo złożone z liter alfabetu wejściowego Ł = {a, b, c} jest
palindromem. Dane słowo jest palindromem wtedy, gdy czyta się tak samo z obu stron. Należy
również przyjąć, że pojedynczy symbol to także palindrom. Wprowadzono również dwa dodatkowe
stany SA i SN. SA to stany akceptacji, a SN oznacza stan nieakceptacji.
Przejście do stanu akceptacji oznacza, że badane słowo jest palindromem. Natomiast jeśli
przejdziemy do stanu nieakceptacji to dane słowo nie jest palindromem. Tabela przejść między
stanami nr 4.4 na stronie 48 pokazuje przykładowe rozwiązanie dla tego problemu.
Szeroki wachlarz problemów stawianych przed Maszyną Turinga dowodzi, że potrafią one
rozwiązać każdy efektywnie rozwiązywalny problem algorytmiczny. Mówiąc prościej Maszyna
Turinga potrafi rozwiązać problem algorytmiczny, dla którego jesteśmy w stanie znalez
ć algo-
rytm możliwy do oprogramowania w dowolnym języku, wykonujący się na pewnym komputerze,
nawet na takim, którego jeszcze nie zbudowano, ale jego zbudowanie jest możliwe. To stwier-
dzenie jest jedną z wersji tak zwanej tezy Churcha  Turinga. Teza ta swoją nazwę wzięła
od nazwisk swych twórców Alonza Churcha oraz Alana M. Turinga, a także od angielskiego
określenia Computability Theory, czyli teorii obliczalności. Należy sobie zdać sprawę, że teza
Churcha  Turinga jest tezą, a nie twierdzeniem, stąd nie da się jej udowodnić w matematycz-
48 Rozdział 4. Maszyna Turinga i automaty skończone

Q

q0 q1 q2 q3 q4 q5 q6 q7 q8 q9 q10 q11
Ł


q0 q2 q10 q0 q5 q10 q0 q8 q10 q0
Ć SA SN
Ć, P Ć, L Ć, P Ć, P Ć, L Ć, P Ć, P Ć, L Ć, P Ć, P
q1 q1 q3 q3 q4 q11 q6 q7 q11 q9
a SA SN
Ć, P a, P Ć, L a, L a, P a, P a, L a, P a, P a, L
q4 q1 q11 q3 q4 q6 q6 q7 q11 q9
b SA SN
Ć, P b, P b, P b, L b, P Ć, L b, L b, P b, P b, L
q7 q1 q11 q3 q4 q11 q6 q7 q9 q9
b SA SN
Ć, P c, P c, P c, L c, P c, P c, L c, P Ć, P c, P
Tabela 4.4. Tabela stanów maszyny Turinga sprawdzającej, czy słowo jest palindromem
nym tego słowa znaczeniu. Nie da się tego zrobić, ponieważ jedno z pojęć, do których się ona
odwołuje, jest nieformalnym i nieprecyzyjnym pojęciem  efektywnej obliczalności .
Wniosek, jaki można wysnuć z tezy Churcha  Turinga jest taki, że najzwyklejszy komputer
domowy, mimo swoich ograniczeń czasu i pamięci wyposażony w prosty język programowania,
jest w stanie rozwiązać takie same problemy arytmetyczne jakie rozwiązuje superkomputer wy-
posażony w najbardziej zaawansowane języki programowania. Zarówno jeden jak i drugi model
komputera nie może rozwiązać problemów nierozstrzygalnych (nieobliczalnych) [4]. Podział ze
względu na rozstrzygalność problemów został przedstawiony na rysunku.
Rysunek 4.6. Sfera problemów algorytmicznych
4.2. Wyrażenia regularne
Wyrażenia regularne często wykorzystywane są przez automaty skończone do opisywania pro-
stych wyrażeń w językach programowania, które same akceptują[5]. W dalszej części rozważań
na temat automatów konieczne staje się zatem wprowadzenie nowych definicji.
4.3. Automaty skończone 49
Niech Ł będzie skończonym zbiorem symboli i niech L, L1, L2 będą zbiorami łańcuchów z
Ł".
Złożeniem L1 i L2, oznaczanym jako L1 L2, będziemy zatem nazywać {xy|x " L1 i y " L2}
 oznacza to, że łańcuchy należące do L1 L2 tworzone są poprzez wypisanie łańcucha z L1
a następnie łańcucha z L2, we wszystkich możliwych kombinacjach, np.: niech L1 = {0, 1}
i L2 = {01, 101}, wtedy złożenie L1 L2 = {001, 0101, 101, 1101}.
Niech L0 = {�} oraz Li = Li-1Li dla i 0.
Domknięciem Kleene ego L, oznaczanym symbolem L", nazywamy zbiór:
"

L" = Li
i=0
Domknięciem dodatnim L, oznaczanym symbolem L+, nazywamy zbiór:
"

L" = Li
i=1
Zatem L" jest zbiorem wszystkich słów otrzymanych w wyniku złożenia dowolnej liczby słów
z L, natomiast L+ eliminuje możliwość wystąpienia zera słów, których złożenie określa się jako �;
np.: domknięcie Kleene ego {1, 0}" = {�, 1, 0, 11, 10, 01, 00, . . .}, zaś domknięcie dodatnie {1, 0}+ =
{1, 0, 11, 10, 01, 00, . . .}.
Analizując wyrażenia regularne i zbiory natkniemy się na następujące reprezentacje:
 Ć jest wyrażeniem regularnym, które określa zbiór pusty,
 � jest wyrażeniem regularnym określającym zbiór {�},
 dla każdego a z Ł, a jest wyrażeniem regularnym określającym zbiór a,
 jeżeli r i s są wyrażeniami regularnymi reprezentującymi odpowiednio języki R i S, to (r+s),
(rs) i (r") są wyrażeniami regularnymi reprezentującymi odpowiednio zbiory R *" S, RS i
R".
Przykład 26. Przykłady reprezentacji zbiorów i wyrażeń regularnych:
00
 00 jest wyrażeniem regularnym, reprezentującym 00
00
(0 + 1)
 (0 + 1) opisuje zbiór wszystkich łańcuchów złożonych z zer i jedynek
(0 + 1)
(0 + 1)"00(0 + 1)"
 (0 + 1)"00(0 + 1)" opisuje zbiór wszystkich zer i jedynek w których przynajmniej raz wystą-
(0 + 1)"00(0 + 1)"
piło podwojenie zer
(1 + 10)"
 (1 + 10)" reprezentuje zbiór wszystkich zer i jedynek rozpoczynających się od 1 i nie zawie-
(1 + 10)"
rających podwojonych symboli 0
(0 + 1)"011
 (0 + 1)"011 opisuje wszystkie łańcuchy zer i jedynek kończące się sekwencją 011
(0 + 1)"011
0+1+2+
 0+1+2+ jest wyrażeniem reprezentującym dowolna liczbę zer po których następuje dowol-
0+1+2+
na liczba jedynek, a następnie dowolna liczba dwójek (domknięcie dodatnie czyli łańcuchy
końcowe muszą zawierać przynajmniej po jednym reprezentancie powyższych symboli).
4.3. Automaty skończone
Kontynuując tematykę rozdziału chcielibyśmy teraz przedstawić typy automatów skończonych.
Wśród automatów skończonych możemy wyróżnić deterministyczny automat skończony
(DAS) oraz niedeterministyczny automat skończony (NAS).
50 Rozdział 4. Maszyna Turinga i automaty skończone
4.3.1. Deterministyczny automat skończony
Jest to abstrakcyjna maszyną o skończonej liczbie stanów, która swoją pracę rozpoczyna w stanie
początkowym, następnie odczytuje kolejne symbole danego słowa. Po wczytaniu stanu automat
zmienia swój stan na stan ściśle uzależniony od poprzedniego stanu. Automat skończony roz-
poczyna pracę od stanu, który nazywamy stanem początkowym i kończy działanie w stanie
nazywanym stanem końcowym. Praca automatu polega na analizie symboli wejściowych ze
skończonego alfabetu. Odczytany symbol wymusza przejście do innego stanu, czasem również
prowadzi do tego samego stanu. Po przeanalizowaniu wszystkich symboli automat skończony
przyjmuje jeden z dwóch stanów: akceptacji lub nieakceptacji[5] . W dalszej części naszych
rozważań automaty skończone będziemy przedstawiać za pomocą grafów skierowanych, w któ-
rych wierzchołki obrazować będą stany automatu. Jeśli zaistnieje przejście z jednego stanu do
następnego, to takie przejście przedstawimy za pomocą łuku. Stan początkowy, wierzchołek roz-
poczynający pracę automatu, oznaczymy przez kółko i strzałkę z napisem start. Stan końcowy
zaakcentujemy przez wprowadzenie dwóch różnych wierzchołków grafu z etykietą A  oznacza-
jącą stan akceptacji oraz N  oznaczającą stan nieakceptacji, stan końcowy oznaczamy podwój-
nym kółkiem. Poniżej przedstawimy formalny zapis deterministycznego automatu skończonego
za pomocą uporządkowanej piątki:
DAS = < Q, Ł, �, q0, F >
DAS = < Q, Ł, �, q0, F >
DAS = < Q,Ł, �, q0, F >
gdzie:
Q
Q  skończony zbiór stanów,
Q
Ł
Ł  skończony alfabet symboli wejściowych. q0 należące do Q jest stanem początkowym od
Ł
którego automat rozpoczyna działanie,
F ą" Q
F ą" Q  zbiór stanów końcowych (akceptacji lub nieakceptacji)
F ą" Q
�
�  funkcja następnego ruchu, będąca odwzorowaniem Q � � - Q. Oznacza to, że funkcja
�
przejścia określa każdemu stanowi q i każdemu zymbolowi na wejściu nowy stan automatu.
Poniżej prezentujemy dwa przykłady grafu przejść i tabeli stanów deterministycznego auto-
matu skończonego:
Przykład 27. Deterministyczny automat skończony akceptujący słowa, w których a i c wystę-
pują zawsze obok siebie (ac lub ca). Dodatkowo przyjmujemy założenie, że słowo czytamy od
lewej strony.
DAS = < Q, Ł, �, q0, F >
DAS = < Q, Ł, �, q0, F >
DAS = < Q,Ł, �, q0, F >
Ł = {Ć, a, b, c}
Tabela stanów o numerze 4.5 będąca rozwiązaniem powyższego problemu jest zaprezento-
wana na stronie 50.
q0 q1 q2 q3
Ć N N N A
a q1 N q3 q1
b 0 N N q3
c q2 q3 N q2
Tabela 4.5. Tabela przejść stanów dla deterministycznego automatu skończonego.
4.3. Automaty skończone 51
Rysunek 4.7. Graf przejść dla deterministycznego automatu skończonego
Słowa, dla których automat prawidłowo wykonuje swoje działanie:
Słowo: bbbacaccacabbb Droga akceptacji: q0, q0, q0, q1, q3, q1, q3, q2, q3, q2, q3, q3, q3, q3,A
Słowo: bbacccab Droga nieakceptacji: q0, q0, q1, q3, q2,N
4.3.2. Niedeterministyczny automat skończony
Niedeterministyczny automat skończony jest maszyną o skończonej liczbie stanów, która roz-
poczyna swoje działanie w stanie początkowym, następnie wczytuje kolejne symbole słowa. Po
wczytaniu każdego symbolu zmienia ona swój stan na inny, będący elementem zbioru stanów. Po
wczytaniu całego słowa maszyna może znalez
ć się w jednym z dwóch stanów: stanie akceptacji
lub nieakceptacji.
Niedeterministyczny automat skończony od deterministycznego automatu skończonego od-
różnia się tym, że wczytany symbol w danym stanie może powodować przejście do jednego
z dwóch różnych stanów [5]. Formalnie niedeterministyczny automat skończony można przed-
stawić jako uporządkowaną piątkę:
NAS = < Q, Ł, �, q0, F >
NAS = < Q, Ł, �,q0, F >
NAS = < Q, Ł,�, q0,F >
gdzie:
Q
Q  skończony zbiór stanów,
Q
Ł
Ł  skończony alfabet symboli wejściowych. q0 należące do Q jest stanem początkowym
Ł
od którego automat rozpoczyna działanie,
F ą" Q
F ą" Q  zbiór stanów końcowych (akceptacji lub nieakceptacji)
F ą" Q
�
�  funkcja przejścia, będąca odwzorowaniem Q � � - 2Q. 2Q jest zbiorem potęgowym,
�
czyli zbiorem wszystkich możliwych podzbiorów zbioru Q.
Przykład 28. Niedeterministyczny automat skończony akceptujący słowa, w których wystąpiła
przynajmniej raz sekwencja symboli abc. Dodatkowo przyjmujemy założenie, że słowo czytamy
od lewej strony.
NAS = < Q, Ł, �, q0, F >
NAS = < Q, Ł, �,q0, F >
NAS = < Q, Ł,�, q0,F >
Ł = {Ć, a, b, c}
Graf przejść nr 4.8 dla powyższego przykładu prezentujemy na stronie 52.
52 Rozdział 4. Maszyna Turinga i automaty skończone
Rysunek 4.8. Graf przejść dla niedeterministycznego automatu skończonego. Droga akceptacji
4.3.3. Automat skończony z �-ruchami
Jest to jest modyfikacja deterministycznego automatu skończonego. Różnica polega na tym, że
w przypadku tego automatu, wyzwalaczem do przejścia pomiędzy stanami może być symbol
pusty �. Należy tutaj podkreślić, że symbol � nie jest tożsamy z symbolem Ć.
Formalnie deterministyczny automat skończony z �-ruchami można przedstawić jako upo-
rządkowaną piątkę:
DAS� = < Q, Ł, �, q0, F >
DAS� = < Q, Ł, �, q0, F >
DAS� = < Q,Ł, �, q0, F >
gdzie:
Q
Q  skończony zbiór stanów,
Q
Ł
Ł  skończony alfabet symboli wejściowych. q0 należący do Q jest stanem początkowym
Ł
od którego automat rozpoczyna działanie,
F ą" Q
F ą" Q  zbiór stanów końcowych (akceptacji lub nieakceptacji)
F ą" Q
�
�  funkcja przejścia, będąca odwzorowaniem Q � � *" {�} - Q. Oznacza to, że funkcja
�
istnieje nie tylko dla każdego stanu i każdego symbolu wejściowego, ale również dla
symbolu �.
Poniżej prezentujemy przykład automatu DAS z �-ruchami:
Przykład 29. Przykład deterministycznego automatu skończonego, który akceptuje słowa re-
prezentowane przez następujące wyrażenie regularne:
W = (0 + 1)+011(101)"
Ł = {Ć, a, b, c}
Należy również przyjąć założenie, że słowo czytamy od lewej strony.
Graf przejść nr 4.9 dla powyższego przykładu prezentujemy na stronie 53.
Poniżej prezentujemy słowa wraz z drogą akceptacji, dla których automat jest działa po-
prawnie:
Słowo: 010001111 Droga akceptacji: q0, q1, q2, q8, q2, q8, q2, q8, q2, q3, q6, q7, q5, q8, q9,A
Słowo: 011 Droga akceptacji: q0, q1, q2, q3, q5, q8, q9,A.
4.4. Konstruktory
Konstruktory diagramów przejść są to gotowe wyrażenia regularne, które umożliwiają stworzenie
pewnego mechanizmu automatu skończonego dla dowolnego wyrażenia [5]. Można wyróżnić trzy
takie postacie wyrażeń regularnych:
 suma teoriomnogościowa: r = r1 + r2
 złożenie r = r1r2
"
 domknięcie r = r1
4.4. Konstruktory 53
Rysunek 4.9. Graf przejść dla DAS z �-ruchami
4.4.1. Konstruktor diagramu przejść dla sumy teoriomnogościowej r = r1 + r2
Rysunek 4.10. Konstruktor diagramu przejść dla sumy teoriomnogościowej
Zarówno pierwsza, jaki i druga droga w zaprezentowanym diagramie nr 4.10 automatu rozpo-
czyna się od przejścia do stanu q1 lub analogicznie do stanu q2 przy pustym wejściu �. Jeśli droga
automatu prowadzi do q1, to w dalszym etapie może dowolnie przebiegać, aż do osiągnięcia stanu
f1, następuje przechodzi do stanu fo, przy pustym wyjściu �. Jeśli natomiast, droga rozpoczęła
się przejściem ze stanu q0 do q2 to następnie przebiega dowolną trasą, aż do osiągnięcia stanu
f2, a następnie przechodzi do stanu f0.
Dowolne drogi przejścia pomiędzy q1 i f1 oraz q2 i f2 należy zaprojektować używając do tego
wyrażeń składowych r1 i r2
4.4.2. Konstruktor dla złożenia r = r1r2
Rysunek 4.11. Konstruktor diagramu przejść dla złożenia r = r1r2
Droga z q1 do f2 w automacie składa się z drogi oznaczanej pewnym łańcuchem prowadzącym
z q1 do f1, po której następuje przejście ze stanu f1 do stanu q2 przy pustym wejściu � a następnie
drogą z q2 do f2.
54 Rozdział 4. Maszyna Turinga i automaty skończone
"
Rysunek 4.12. Konstruktor diagramu przejść dla domknięcia r = r1
"
4.4.3. Konstruktor dla domknięcia r = r1
Droga prowadząca z q0 do f0 może być dwojakiego rodzaju: albo będzie przebiegać z q0 do
f0 po etykiecie �, albo z drogi od q0 do q1 przy etykiecie �, po których następuje określona
liczba (w niektórych przypadkach również 0) dróg z f1 do q1. Następnie droga przebiegać będzie
pomiędzy q1 a f1, aż w końcu drogą z f1 do f0 przy etykiecie �.
Przedstawione wyżej konstrutory będą przydatne przy tworzeniu diagramu przejść stanów
NAS dla wyrażeń regularnych. Proces ten należy rozpocząć od rozkładu wyrażenia regularnego
na elementarne składowe, dla których będziemy mogli tworzyć automaty, te natomiast na pod-
stawie konstruktorów łączymy w logiczną całość. Poniżej zaprezentujemy przykład automatu
akceptującego wyrażenie regularne 01" + 1.
To wyrażenie jest postaci: r = r1 + r2 gdzie: r1 = 01"; r2 = 1. Dla wyrażenia r2 postać
automatu jest następująca:
Rysunek 4.13. Automat dla wyrażenia r2
wyrażenie r1 zapiszemy jako r1 = r3 + r4 gdzie r3 = 0; r4 = 1". Automat dla r3 przedsta-
wiamy poniżej:
Rysunek 4.14. Automat dla wyrażenia r3
"
następnie wyrażenie r4 możemy zapisać jako r4 = r5 gdzie r5 to 1, a NAS dla r5 to:
Rysunek 4.15. Automat dla wyrażenia r5
Następnie powyższe konstruktory zostaną wykorzystane dla przedstawienia automatu dla
wyrażenia r4 = 1" (konstruktor domknięcia):
Kolejno dla r1 = r3r4 (r1 = 01") wykorzystujemy wcześniej zdefiniowane konstruktory z
rysunków 4.14 oraz 4.16. Dzięki tej operacji powstaje następujące złożenie:
Ostatecznie tworzymy konstrukcję dla wyrażenia r = r1 + r2 (r = 01" + 1) wykorzystując
konstruktor sumy teoriomnogościowej.
4.4. Konstruktory 55
Rysunek 4.16. Konstruktor domnkięcia
Rysunek 4.17. Konstruktor dla r1 = r3r4 (r1 = 01")
Rysunek 4.18. NAS z �-ruchami dla wyrażenia regularnego r = 01" + 1
Rozdział 5
Gramatyki i języki formalne
W tym rozdziale zostaną zdefiniowane takie pojęcia jak gramatyka, semantyka i syntaktyka,
a także gramatyka bezkonstekstowa. Wyjaśniona zostanie klasyfikacja Chomsky ego. Rozdział
ten obejmuje również informacje dotyczące notacji Backusa-Naura, która wykorzystywana jest
do definiowania gramatyk bezkontekstowych wraz z przykładami.
5.1. Gramatyki  podstawowe informacje
Gramatyka to układ reguł, zbiór słów utworzonych z symboli języka. Słowa mogą być interpre-
towane jako obiekty językowe różnego typu np.: jako formy wyrazowe, grupy wyrazów i zdania.
Gramatykę języka można rozpatrywać jako zbiór powtarzających się reguł budowy zdań nazy-
wanych syntaktyczną strukturą języka.
Syntaktyka  czyli składnia języka to reguły budowy zdań języka lub budowy konstrukcji
językowych.
Semantyka języka jest to interpretacja tych reguł, zasady stosowania składni.
Gramatyki formalne zajmują się pojęciami abstrakcyjnymi powstałymi na drodze uogólnień
pojęcia formy wyrazowej, grupy wyrazów czy zdania. O ile zwykłe gramatyki umożliwiają okre-
ślenie zbioru reguł budowy zdań, o tyle gramatyki formalne stanowią pewien sposób badania
i opisu zbioru reguł[5] [6]. Wyróżnia się trzy typy gramatyk formalnych:
 rozpoznająca  jest gramatyką, która dla dowolnego słowa potrafi rozstrzygnąć, czy jest
ono poprawne czy też nie. W przypadku uzyskania odpowiedzi pozytywnej gramatyka ta
potrafi podać wskazówki dotyczące budowy badanego słowa,
 generacyjna  gramatyka ta potrafi zbudować dowolne słowo poprawne, równocześnie po-
dając wskazówki dotyczące jego budowy; w procesie tworzenia słów nie powstają niepopraw-
ne słowa,
 przetwarzająca  dla dowolnie poprawnie zbudowanego słowa gramatyka potrafi zbudować
jego odwzorowania. Odwzorowania te mają postać słowa poprawnego; w procesie tworzenia
odwzorowań gramatyka dodatkowo określa wskazówki dotyczące kolejności stosowania od-
wzorowań.
5.2. Gramatyki bezkontekstowe
Gramatyka bezkontekstowa jest podstawą formalizowania języków i ich analizy syntaktycznej,
jest też podstawą upraszczania analityki języków programowania. Gramatyki bezkontekstowe to
skończony zbiór zmiennych, wśród których wyróżniamy symbole pomocnicze (zwane też niekoń-
cowymi) i symbole pierwotne (zwane końcowymi). Symbole te są powiązane w reguły nazywane
produkcjami[5]. Dlatego gramatyki bezkontekstowe możemy przedstawić jako uporządkowaną
czwórkę:
G =< V, T, P, S >
G =< V, T, P,S >
G =< V, T,P, S >
gdzie:
V
V  to alfabet końcowy (zasadniczy). Jest to zbiór symboli terminalnych  skończony niepusty
V
G
zbiór symboli gramatyki G Alfabet końcowy jest to zbiór elementów pierwotnych, z których
G.
58 Rozdział 5. Gramatyki i języki formalne
budowane są słowa generowane przez gramatykę,
T
T  to alfabet pomocniczy. Jest to zbiór symboli nieterminalnych (inaczej niekońcowych) 
T
którymi oznacza się klasy lub słowa złożone z elementów pierwotnych. Inaczej mówiąc: jest to
słownik typów syntaktycznych,
P
P  to zbiór produkcji. Są to reguły gramatyki, czyli skończony zbiór reguł tworzenia nowych
P
S
słów. S  to głowa gramatyki. Jest to wyróżniony symbol pomocniczy oznaczający klasę tych
S
wszystkich obiektów językowych, dla których opisu przeznaczona jest gramatyka.
A
Słownik A to zbiór słów będących sumą teoriomnogościową alfabetu końcowego i pomocniczego
A
A = ( V *" T )
Notacja Backusa-Naura (z ang. Backus-Naur form) jest sposobem zapisu reguł gramatyki
bezkontekstowej, czyli sposobem opisu języków formalnych. Jest ona również powszechnie uży-
wana w informatyce do zapisu składni języków programowania i protokołów komunikacyjnych.
Notacja ta została wymyślona przez Johna Backusa w latach 50-tych w czasie prac nad językiem
Fortran, a następnie została zmodyfikowana przez Petera Naura i użyta do zdefiniowania składni
języka Algol. Zadaniem tej notacji jest definiowanie składni języka za pomocą definicji syntak-
tycznych, w których występują zmienne metajęzykowe, czyli symbole nieterminalne, a także
symbole terminalne.
Zmienne metajęzykowe będziemy zapisywać w nawiasach kątowych <>, natomiast regułę
podstawiania zaakcentujemy przez symbol -.
Przykład 30. -
-
-
- chłopiec
- mały

5.3. Język wyrażeń algebraicznych
Język wyrażeń algebraicznych możemy przedstawić za pomocą następujących produkcji grama-
GBK = V, T, P, S
tyk bezkontekstowych GBK = V, T, P,S
GBK = V, T,P, S :
 - +
 - 
 - *
 - /
 - ()
 - id
Język ten definiuje wyrażenie arytmetyczne z operatorami +, -, ", / oraz argumentami re-
prezentowanymi przez symbol id. Początkowe produkcje mówią, że wyrażenie może być złożone
z dwóch wyrażeń połączonych znakiem dodawania, odejmowania, mnożenia lub dzielenia. Ko-
lejna produkcja prezentuje wyrażenie, które jest innym wyrażeniem ujętym w nawiasy. Ostatnia
przedstawia, że pojedynczy argument również może być wyrażeniem. Poniżej zostaną przedsta-
wione produkcje złożone w wyrażenia:
 =�! *
 =�! () *
 =�! * id
 =�! ( + ) * id
 =�! + id) * id
5.4. Drzewo wywodu dla gramatyki bezkontekstowej 59
 =�! (id + id) * id
Symbol =�! oznacza zastąpienie zmiennej znajdującej się po lewej stronie, prawą stroną
produkcji dla tej zmiennej  jest to wyprowadzenie tej zmiennej.
5.4. Drzewo wywodu dla gramatyki bezkontekstowej
Drzewo D jest wyprowadzalne dla gramatyki bezkontekstowej jeśli spełnione zostaną następu-
jące warunki:
 każdy wierzchołek drzewa D ma etykietę będącą symbolem V albo T lub słowem pustym,
 etykieta wierzchołka, który jest korzeniem drzewa D nosi nazwę głowy gramatyki i oznaczona
jest symbolem S,
 jeżeli wierzchołek wewnętrzny drzewa opatrzony jest etykietą A, to A musi należeć do zbioru
V (zbiór V to zbiór symboli pomocniczych),
 jeżeli wierzchołek n drzewa D ma etykietę A, oraz wierzchołki n1, n2, . . . , nk są potomkami
wierzchołka n uszeregowanymi od lewej do prawej strony drzewa oraz są one opatrzone
etykietami X1, X2, X3, . . . Xk to musi istnieć produkcja A - X1, X2, X3. Produkcja ta
należy do P  jest zatem produkcją gramatyki bezkontekstowej (GBK).
Jeżeli wierzchołek n drzewa ma etykietę � to wierzchołek ten jest liściem drzewa D; jest
on również jedynym synem swego ojca. Etykiety liści czytane są od lewej do prawej stają się
plonem drzewa rozkładu.
Przykład 31. Rozpatrzmy gramatykę G = ({S, A}, {a, b}, {P, S}), gdzie P składa się z nastę-
pujących produkcji:
S - aAS | a
A - SbA | SS | ba
Wywód dla tej gramatyki: S =�! aAS =�! aSbAS =�! aabAS =�! aabbaS =�! aabbaa, zaś
drzewo wyprowadzenia pokazane zostało na rysunku 5.1.
Rysunek 5.1. Drzewo wyprowadzenia gramatyki
Dwa drzewa wyprowadzeń są tożsamościowo równe, jeżeli posiadają taką samą strukturę
gałęzi oraz są zaopatrzone w jednakowe etykiety przy tych samych węzłach. Liczba reguł musi
być skończona, natomiast liczba znaczników może być nieskończona, wówczas mogą istnieć takie
symbole alfabetu pomocniczego, które powtarzają się w znacznikach struktury dowolną ilość
razy. Dodatkowo, mogą istnieć takie łańcuchy drzewa, które zawierają pewien symbol więcej
niż n razy dla dowolnego z góry ustalonego n.
Dla zdefiniowania języka generowanego przez gramatykę GBK =< V, T, P, S > wprowadz
-
my notację do reprezentowania wyprowadzeń. Pierwszym krokiem będzie zdefiniowanie dwóch
60 Rozdział 5. Gramatyki i języki formalne
"
=�! =�!
relacji wyprowadzenia: i . Relacje te łączą dwa łańcuchy słów utworzonych z symboli
G G
pomocniczych lub symboli końcowych. Jeśli A - � jest produkcją z P, natomiast symbole
ą i ł są dowolnymi symbolami z alfabetu, to mówimy, że ąAł =�!G ą�ł jest wyprowadzalne.
Mówimy, że produkcja A - � zastosowana do łańcucha ąAł daje w wyniku ą�ł, albo
inaczej: że ą�ł jest bezpośrednio wyprowadzalne z ąAł w gramatyce G.
A - �
ą, ł " (V *" T )"  zbiór wszystkich słów nad tym alfabetem
ąAł =�!G ą�ł
Dwa łańcuchy są związane relacją bezpośredniej wyprowadzalności, gdy drugi z nich można
otrzymać, z pierwszego poprzez zastosowanie jednej z produkcji P. Przypuśćmy, że ą1, ą2, � � � , ąm
są łańcuchami z (V *" T )", m 1, oraz ą1 =�!G ą2, ą2 =�!G ą3, . . . ąm-1 =�!G ąm wtedy
piszemy:
"
=�!
ą1 ąm
G
i mówimy, że ąm jest wyprowadzalne z ą1 w gramatyce G.
Przykład 32. Mamy gramatykę G =< V, T, P, S >, gdzie V = {S}, T = {a, b}, i P = {S -
aSb, S - ab}. Jedyną zmienną jest tu S, a i b są symbolami końcowymi. Istnieją dwie produk-
cje: S - aSb oraz S - ab. Stosując pierwszą z nich n - 1 razy, a następnie jeden raz drugą
otrzymujemy:
S =�! aSb =�! aaSbb =�! a3Sb3 =�! . . . =�! an-1Sbn-1 =�! anbn
5.5. Klasyfikacja Chomsky ego
Podstawowym obiektem zastosowań teorii gramatyk nie są dowolne gramatyki, lecz gramatyki
szczególnych typów, które są najważniejsze zarówno z teoretycznego jak i praktycznego punktu
widzenia. Wyróżnienia tych typów dokonuje się na podstawie reguł. W teorii Chomsky ego
można wyróżnić cztery typy gramatyk. Gramatyki te wyodrębnia się poprzez nakładanie coraz
silniejszych ograniczeń na układ reguł P:
 gramatyka klasy 0  charakteryzuje się ona tym, że wszystkie produkcje mają postać:
u - w, u " A" = {�}, w " A" = {�}, gdzie A" = (V *" T )". A" to ciąg znaków pomocni-
czych, tworzonych na bazie słownika A = (V *" T ).
 gramatyka klasy 1  zwana gramatyką kontekstową. Jest to gramatyka, która charakte-
ryzuje się tym, że wszystkie produkcje mają postać: uXw - ubw, u, w " A", A " S, X 
symbol pomocniczy, b jest elementem znaków końcowych gdzie b " A"
{�}.
 gramatyka klasy 2  zwana gramatyką bezkontekstową, która w układzie reguł P dopusz-
cza jedynie reguły postaci X - b, A " S, b " A"\{�},
 gramatyka klasy 3  zwana gramatyką regularną, która w układzie reguł P dopuszcza
reguły postaci:
 X - bY  gramatyki prawostronnie regularne,
 X - Y b  gramatyki lewostronnie regularne,
"
A " S, B " S *" {e}, b " T \{�}.
Element syntaktyczny nazywany jest elementem rekursywnym, wtedy gdy dla pewnego z gó-
ry ustalonego n istnieje takie drzewo struktury, którego łańcuch zawiera ten symbol jako nazwę
węzła więcej niż n razy[6]. Zatem wyodrębnić należy trzy rodzaje elementów rekursywnych:
 element A nazywa się leworekursywnym, jeżeli podporządkowane mu drzewo zawiera A tylko
w łańcuchu wysuniętym najbardziej w lewo,
5.5. Klasyfikacja Chomsky ego 61
 element A nazywa się praworekursywnym, jeżeli podporządkowane mu drzewo zawiera A tyl-
ko w łańcuchu wysuniętym najbardziej w prawo,
 element A nazywa się samozanurzającym, jeżeli podporządkowane mu drzewo zawiera A w pew-
nym łańcuchu wewnętrznym.
Rysunek 5.2. Elementy rekursywne: leworekursywne, samozanurzające i praworekursywne
Spis tabel
1.1. Tabela przesunięć binarnych dla liczb ujemnych . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2. Tabela operacji dodawania i odejmowania w trzech kodach zapisu . . . . . . . . . . . . . . . 13
1.3. Tabela funkcji XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1. Tabela operacji iloczynu logicznego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2. Tabela operacji sumy logicznej . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3. Tabela operacji negacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4. Tabela prawdy dla rozdzielności mnożenia względem dodawania. . . . . . . . . . . . . . . . . 27
2.5. Tabela prawdy dla rozdzielności dodawania względem mnożenia. . . . . . . . . . . . . . . . . 27
2.6. Tabela postulatów Huntingtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.7. Zestawienie twierdzeń algebry Boole a i postulatów Huntingtona . . . . . . . . . . . . . . . . 31
2.8. Tablica funkcji boolowskich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1. Tabela ograniczników i priorytetów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2. Tabela priorytetów ograniczników z elementami logicznymi . . . . . . . . . . . . . . . . . . . 39
3.3. Przykład algotyrmu z konwersją wyrażeń z instrukcją warunkową . . . . . . . . . . . . . . . 40
3.4. Przykład przejścia z ONP na język symboliczny . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1. Tabela stanów maszyny Turinga podwajająca symbole w słowie dla alfabetu wejściowego
Ł = {a, b} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2. Tabela wyrażeń dla rezalizowanego przykładu maszyny Turinga. . . . . . . . . . . . . . . . . 46
4.3. Tabela stanów maszyny Turinga realizując operację odejmowania dla alfabetu wejściowego
Ł = {1, -, +, 0, =} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4. Tabela stanów maszyny Turinga sprawdzającej, czy słowo jest palindromem . . . . . . . . . . 48
4.5. Tabela przejść stanów dla deterministycznego automatu skończonego. . . . . . . . . . . . . . 50
Spis rysunków
1.1. Kod pozycyjny, system dziesiętny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Diagram Venna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1. Schemat tworzenia programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2. Model automatu ze stosem do translacji wyrażeń arytmetycznych . . . . . . . . . . . . . . . 36
3.3. Schemat dla przykładu przejścia z postaci postfiksowej na infiksową . . . . . . . . . . . . . . 38
3.4. Schemat blokowy instrukcji if-then-else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1. Podstawowy model Maszyny Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2. Graf przejść między stanami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3. Fragment tabeli przejść dla powyższego przykładu . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4. Fragment tabeli przejść dla powyższego przykładu . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5. Tabela stanów oraz graf przejść maszyny Turinga dodającej 1 do liczby binarnej . . . . . . . 47
4.6. Sfera problemów algorytmicznych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7. Graf przejść dla deterministycznego automatu skończonego . . . . . . . . . . . . . . . . . . . 51
4.8. Graf przejść dla niedeterministycznego automatu skończonego. Droga akceptacji . . . . . . . 52
4.9. Graf przejść dla DAS z �-ruchami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.10. Konstruktor diagramu przejść dla sumy teoriomnogościowej . . . . . . . . . . . . . . . . . . . 53
4.11. Konstruktor diagramu przejść dla złożenia r = r1r2 . . . . . . . . . . . . . . . . . . . . . . . 53
"
4.12. Konstruktor diagramu przejść dla domknięcia r = r1 . . . . . . . . . . . . . . . . . . . . . . . 54
4.13. Automat dla wyrażenia r2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.14. Automat dla wyrażenia r3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.15. Automat dla wyrażenia r5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.16. Konstruktor domnkięcia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.17. Konstruktor dla r1 = r3r4 (r1 = 01") . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.18. NAS z �-ruchami dla wyrażenia regularnego r = 01" + 1 . . . . . . . . . . . . . . . . . . . . . 55
5.1. Drzewo wyprowadzenia gramatyki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2. Elementy rekursywne: leworekursywne, samozanurzające i praworekursywne . . . . . . . . . 61
Bibliografia
[1] Władysław M Turski: Propedeutyka informatyki. PWN, Warszawa, 1977.
[2] B. Pochopień: Arytmetyka systemów cyfrowych. Politechnika Śląska-Skrypt uczelniany nr 1841,
Gliwice, 1994.
[3] Kenneth A. Ross, Charles R. B. Wright Matematyka dyskretna. Wydawnictwo Naukowe PWN,
Warszawa 2003.
[4] Dawid Harel: Rzecz o istocie informatyki. WNT, Warszawa, 1992.
[5] John E. Hopcroft, Jefrey D. Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. PWN,
Warszawa, 1994.
[6] Zoja Ałfierowa: Teoria algorytmów. PWN, Warszawa, 1977.
[7] Stanisław Kozielski: Zbiór zadań z podstaw informatyki. Politechnika Śląska-Skrypt uczelniany
nr 1842, Gliwice, 1994.