Arytmetyka binarna 2
ROZWINIĘCIE DWÓJKOWE 2
REGUŁA ZAMIANY 3
Kody znak -moduł 3
Kod uzupełnienia do 1 - ZU1 4
Kod uzupełnienia do 2 - ZU2 4
Dodawanie i odejmowanie liczb binarnych 4
DZIAŁANIA NA LICZBACH ZAPISANYCH W KODACH BINARNYCH: ZM, ZU1, ZU2 4
Dodawanie A+B w kodzie Znak - Moduł ZM 5
Dodawanie A+B w kodzie ZU1 5
Dodawanie A+B w kodzie ZU2 5
Mnożenie i dzielenie liczb binarnych 6
PRZESUWANIE LICZB ZE ZNAKIEM 6
PRZESUWANIE LICZB 6
METODY MNOŻENIA LICZB W SYSTEMIE DWÓJKOWYM 6
METODA MNOŻENIA BEZPOŚREDNIEGO 6
MNOŻENIE METODĄ BOOTH'A 6
I wariant metody Booth'a 6
II wariant metody Booth'a: 7
DZIELENIE LICZB BINARNYCH 8
Metoda porównawcza - jest stosowana w zapisie znak moduł (ZM) i gdy jest spełniony warunek A<B, gdzie: 8
Metoda restytucyjna - to metoda dzielenia dwóch liczb zapisanych w kodzie znak moduł (ZM) i gdy |A|<|B|. 10
Logika binarna 10
Algebra Boole'a - podstawowe definicje: 11
Aksjomatyczna definicja algebry Boole'a - postulaty Huntigtona: 11
Algebra Boole'a dwuwartościowa: 11
Podstawowe twierdzenia i własności algebry Boole'a: 12
Funkcje Boolowskie: 13
ZASADY AUTOMATYCZNEJ TRANSLACJI 14
Translacja i translatory 14
Stos i odwrotna notacja polska (ONP) 14
Translacja wyrażeń arytmetycznych 15
AUTOMAT SKOŃCZONY 19
Deterministyczny automat skończony 19
Niedeterministyczny automat skończony 23
-ruchami 24εAutomat skończony z
Wyrażenia regularne 25
Zastosowania automatów skończonych 28
Analizatorów leksykalnych 28
Edytorów tekstu 28
Techniki 28
MASZYNA TURINGA 28
Podstawowy model maszyny Turinga 28
Arytmetyka binarna
ROZWINIĘCIE DWÓJKOWE
Jednym z najlepiej znanych sposobów kodowania informacji zawartej w liczbach jest kodowanie w dziesiątkowym systemie pozycyjnym, w którym dla przedstawienia liczb naturalnych używamy dziesięciu różnych znaków - cyfr : 0,1...,9, Dla przedstawienia dowolnych liczb całkowitych - jedenastu różnych znaków: cyfr oraz znaku “minus”, a dla przedstawienia liczb wymiernych - dwunastu znaków: cyfr, znaku “minus” i znaku kropki albo przecinka oddzielającego część całkowitą od części ułamkowej.
Dziesiątkowy system pozycyjny nie jest jedynym sposobem kodowania liczb z jakim mamy na co dzień do czynienia.
Ze względu na przystosowanie urządzeń informatyki do pracy z dwójkowymi ciągami kodowymi, w elektronicznych systemach liczących przedstawiamy liczby (jak i pozostałe wiadomości) w kodzie dwójkowym. W zasadzie stosuje się dwa sposoby kodowania - tzw. dwójkowe kodowanie cyfr dziesiątkowych, przy którym ciągi kodowe są przypisane poszczególnym cyfrom dziesiątkowego rozwinięcia pozycyjnego (tzw. kod BCD, ang. Binary Coded Decimals) oraz dwójkowy system pozycyjny tj. przedstawienie liczb w systemie pozycyjnym o podstawie dwa.
W dwójkowym systemie pozycyjnym do zapisu liczb naturalnych używamy dwu różnych znaków: cyfr dwójkowych 0 i 1. Cyfry dwójkowe nazywamy także binarnymi (ang. binary digit - dwójkowa cyfra).
Naturalny kod binarny (NB) można określić wzorem:
Sposób określenia słowa A w kodzie NB, gdy jest dane słowo reprezentujące liczbę nieujemną
w powszechnie stosowanym kodzie dziesiętnym, wynika z wyżej podanego wzoru i jest następujący:
• gdy dana liczba jest całkowita, to kolejne bity słowa A, począwszy od bitu a0 aż do bitu
an-1, są kolejnymi resztami z dzielenia tej liczby, lub otrzymanego w poprzednim kroku ilorazu przez 2;
• gdy dana liczba jest ułamkowa, to kolejne bity słowa A, od bitu a-1 aż do bitu a -m., są kolejnymi częściami całkowitymi iloczynu tej liczby, lub otrzymanej w poprzednim kroku części ułamkowej, przez 2;
• gdy dana liczba zawiera część całkowitą i część ułamkową, to dla każdej z nich określamy odrębnie bity słowa A
PRZYKŁAD:
L(A)10=23,625
L(A)2 =?
23=11*2+1 a0
11= 5*2+1 a1
5= 2*2+1 a2
2= 1*2+0 a3
1= 0*2+1 a4
0= 0*2+0 a5
.
.
.
0 an-2
0,625
* 2
a -1 (1),250
* 2
a -2 (0),500
* 2
a -3 (1),000
* 2
a -4 (0),000
.
.
.
a -m 0
L(A)2 = 0...010111,1010...0
Istnieją dwa sposoby zapisu liczb:
• system pozycyjny, w którym każda cyfra może przybierać różne wartości w zależności od jej położenia w liczbie ,
• system nie pozycyjny, w którym wartość cyfr nie zależy od jej miejsca w liczbie.
W systemie pozycyjnym odpowiednim położeniom cyfry w liczbie są przyporządkowane odpowiednie “wagi” stanowiące o wartości nominalnej cyfry w liczbie. “Wagi” te, to kolejne naturalne potęgi dowolnej liczy. Od tej liczby najczęściej pochodzi nazwa i tak, jeżeli jest to 2 to system nazywamy dwójkowym, jeżeli 5 to piątkowym. Wagi te stanowią o podstawie liczenia systemu zapisu liczb.
REGUŁA ZAMIANY
Aby zamienić liczbę przedstawioną w systemie liczenia o podstawie “p” na liczbę przedstawioną
w systemie liczenia o podstawie “c”, gdzie q = pn, n N grupujemy na lewo i prawo od przecinka cyfry liczby o podstawie liczenia “p” (po n w grupie) i każdą z tych grup zapisujemy w systemie liczenia o podstawie “q”.
Aby zamienić liczbę przedstawioną w systemie liczenia o podstawie “p” na liczbę przedstawioną
w systemie liczenia o podstawie “q”, gdzie p = qn, n N każdą z cyfr w systemie liczenia o podstawie “p” zapisujemy jako n - cyfrową liczbę w systemie liczenia o podstawie “q”.
Aby przedstawić liczbę całkowitą przedstawioną w systemie o podstawie liczenia “p” na liczbę przedstawioną w systemie liczenia o podstawie “q” dokonujemy dzielenia tej liczby przez “q” zapisanej w systemie o podstawie “p” aż do otrzymania reszty mniejszej od “q”. Otrzymane reszty częściowe zamienia się na system o podstawie “q”, natomiast dzielenie wykonuje się w systemie o podstawie “p”.
Dla liczb ułamkowych algorytm ten jest podobny z tym, że zamiast dzielenia dokonujemy mnożenia. Kolejno otrzymane cyfry części całkowitej są cyframi nowej liczby w systemie liczenia o podstawie “q”.
Czynność mnożenia jest wykonywana tak długo aż wyzerujemy część ułamkową. W innym przypadku uzyskujemy tak zwany k - ty redukt rozwinięcia tego ułamka (gdzie k jest dokładnością dokonywanych obliczeń).
PRZYKŁAD
L(A)10 = 247
L(A)5 = ?
247 / 5 2
49 / 5 4
9 / 5 4
1 1
L(A)5 = (1442)5 = 1 * 53+4 * 52 + 4 * 51 + 2 * 50
L(A)10 = 0,0325
L(A)4 = ?
0,0325 * 4 0
0,13 * 4 0
0,52 * 4 2
2,08 * 4 0
0,32 * 4 1
1,28 * 4 1
1,12
L(A)4 = (0.002011)4 - 6-ty redukt rozwinięcia
Kody znak -moduł
Dla liczb dwójkowych q= 2
Kod uzupełnienia do 1 - ZU1
Spełnia się zależność
jeżeli an-1 = 0, to L(A)
Wynika stąd, że kod ZU1 jest kombinacją kodów. Liczby nieujemne są reprezentowane w naturalnym kodzie binarnym notacji dodatniej, a liczby niedodatnie - w dualnym kodzie naturalnym binarnym notacji dodatniej.
Kod uzupełnienia do 2 - ZU2
Kod zu2 notacji ujemnej jest zadany wzorem:
Aby zapisać liczbę w kodzie ZU1 należy liczbę w kodzie ZM zanegować na wszystkich pozycjach, za wyjątkiem pozycji an-1( bit znakowy).
Aby otrzymać liczbę w kodzie ZU2 należy zapisać ją w kodzie ZM, a następnie licząc od końca wszystkie cyfry przepisać zamieniając je na przeciwne, za wyjątkiem pierwszej jedynki. Cyfra znaku pozostaje bez
Dodawanie i odejmowanie liczb binarnych
DZIAŁANIA NA LICZBACH ZAPISANYCH W KODACH BINARNYCH: ZM, ZU1, ZU2
Operacje dodawania i odejmowania w kodzie Znak - Moduł ZM odbywają się według poniższej tabeli:
Operacja an-1 bn-1 Operacja wykonywana Znak sumy
Dodawanie
Jednakowe
Różne
Odejmowanie Jednakowe
Różne
Uwaga:
gdy w = 1, wówczas Z* ma postać ZU2
A*, B* - cyfry liczby;
zn-1, an-1, bn-1 - znak liczby (1 cyfra)
w - pożyczka
W przypadku kodu ZU1 dodajemy i odejmujemy cyfry liczb wraz ze znakiem. Jeżeli występuje przepełnienie lub pożyczka to uwzględniamy ją poprzez dodanie lub odjęcie od najmniej znaczącej pozycji.
W przypadku kodu ZU2 nie uwzględniamy przepełnienia czy pożyczki, a operacje są wykonywane również na znaku.
Przy wykonywaniu działań dodawania i odejmowania w ZU1 i ZU2 musimy zawsze uwzględniać to, na ilu pozycjach musi być zapisany wynik. Trzeba o tym pamiętać ze względu na to aby przepełnienie nie nastąpiło przy dodawaniu bitów znaku. Dlatego liczby przed operacją dodawania lub odejmowania zapisujemy na k+1 pozycjach, gdzie k jest liczą pozycji dla składnika o większym module.
PRZYKŁAD:
- L(A)ZM= 0.0000111
- L(B)ZM =1.000101 L(B)ZU1 = 1.111010 L(B)ZU2 = 1.111011
Dodawanie A+B w kodzie Znak - Moduł ZM
Dodajemy 0 na k + 1 -ej pozycji oraz liczbę B uzupełniamy cyfrą 0, aby obie miały identyczną ilość pozycji; wykonujemy operację odejmowania, gdyż są różne bity znakowe
Znak wyniku zn-1 = , bo w = 1, czyli zn-1 = 1
Wynik dodawania jest w ZU2 (bo w=1): (1.1,1111101)ZU2 = (1.0,0000011)ZM
(1.1,1111101)ZU2 =(1.0,0000011)ZM=
Dodawanie A+B w kodzie ZU1
Dodajemy 0 dla A i 1 dla B na k+1-ej pozycji oraz uzupełniamy cyfrą 1, aby obie liczby miały tę samą ilość pozycji; dodajemy liczby wraz z bitem znakowym.
Wynik jest w kodzie ZU1
(1.1,1111100)ZU2 = (1.0,0000011)ZM =
Dodawanie A+B w kodzie ZU2
Dodajemy 0 dla A i 1 dla B na k+1-ej pozycji i liczbę B uzupełniamy cyfrą 0, aby obie liczby miały tę samą ilość pozycji; dodajemy wraz z bitem znakowym.
Wynik jest w kodzie ZU2
(1.1,1111101)ZU2 = (1.0,0000011)ZM =
Mnożenie i dzielenie liczb binarnych
PRZESUWANIE LICZB ZE ZNAKIEM
Przesuwanie liczb jest jednoznaczne z mnożeniem danej liczby przez 2i (gdy przesuwamy liczbę mnożoną przez 2i w lewo o " i" pozycji) i dzieleniem, czy też mnożeniem przez 2-i (gdy przesuwamy liczbę mnożoną przez 2-i w prawo o "i" pozycji.)
PRZESUWANIE LICZB
Liczba dodatnia i ujemna w kodzie ZM ZNAK BEZ ZMIAN PRZY PRZESUNIĘCIU WSZYSTKIE DODANE CYFRY SĄ ZERAMI
Liczba ujemna w postaci kodu ZU1 ZNAK BEZ ZMIAN PRZY PRZESUNIĘCIU WSZYSTKIE CYFRY DODANE SĄ JEDYNKAMI
Liczba ujemna w postaci kodu ZU2 -------------------- PRZY PRZESUNIĘCIU W LEWO DODAJEMY ZERA PRZY PRZESUNIĘCIU W PRAWO DODAJEMY JEDYNKI
PRZYKŁAD:
L(A) = (-6)10
Kod Znak - Moduł ZM
1.0110 * 21 = 1.1100 = -12
1.0110 * 2-1 = 1.0011 = -3
Kod ZU1
1.1001 * 21 = 1.0011 = -12
1.1001 * 2-1 = 1.1100 = -3
Kod ZU2
1.1010 * 21= 1.0100 = -24 + 22 = -16 + 4 = -12
1.1010 * 2-1= 1.1101 = -24 + 23 + 22 + 20= -16 + 13 = -3
METODY MNOŻENIA LICZB W SYSTEMIE DWÓJKOWYM
Mnożenie można przeprowadzić wykorzystując następujące metody:
metoda mnożenia bezpośredniego,
metoda Burksa - Goldsteine'a - von Neumanna,
I metoda Robertsona,
II metoda Robertsona,
metoda Bootha.
METODA MNOŻENIA BEZPOŚREDNIEGO
Jest stosowana do liczb zapisanych w kodzie ZM. Mnożenie w tej metodzie przebiega tak jak mnożenie pisemne liczb dziesiętnych, zatem jest ono zastąpione wielokrotnym dodawaniem odpowiednio przesuniętej mnożnej.
MNOŻENIE METODĄ BOOTH'A
I wariant metody Booth'a
Porównywanie par bitów mnożnika (w ZU2). Badamy ostatnie pary bitów (cyfr) mnożnika.
Jeżeli badana para jest kombinacją 1 0, to od iloczynu częściowego odejmujemy mnożną L(A) i przesuwamy wynik o jedno miejsce w prawo (*2-1).
Jeżeli badana para jest odpowiednio parą 0 1, to dodajemy mnożną do iloczynu częściowego i przesuwamy cały wynik o jedno miejsce w prawo.
Jeżeli badana para jest parą o jednakowych cyfrach 0 0 lub 1 1, to wykonujemy tylko przesunięcie w prawo.
Jeżeli w skład wchodzi bit znakowy (znak), to nie wykonujemy przesunięcia.
PRZYKŁAD :
Dla I wariantu metody Booth'a
L(A) = = (0.00111)ZM
L(B)= = (1.00001)ZM = (1.11111)ZU2
Do liczby B na najmniej znaczącej pozycji dopisujemy 0, zatem:
L(B) = (1.111110)ZU2
Badamy kolejne bity mnożnika (czyli kolejne bity liczby B):
para 1-0 - od iloczynu częściowego odejmujemy mnożną (iloczyn częściowy wynosi na początku 0), następnie przesuwamy wynik o jedno miejsce w prawo,
para 1-1 - przesuwamy iloczyn częściowy o jedno miejsce w prawo,
para 1-1 - przesuwamy iloczyn częściowy o jedno miejsce w prawo,
para 1-1 - przesuwamy iloczyn częściowy o jedno miejsce w prawo,
para 1-1 - przesuwamy iloczyn częściowy o jedno miejsce w prawo.
Wynik: (1.1111111001)ZU2 = (1.0000000111)ZM =
II wariant metody Booth'a:
Przesuwamy mnożną o jedno miejsce w prawo (uzyskujemy A/2 - “A - pół”).
Zbadamy ostatni bit mnożnika, jeżeli jest on równy 1, to dodajemy mnożną do iloczynu częściowego, który jest równy zeru na początku mnożenia, jeżeli ostatni bit mnożnika jest równy 0, to nie wykonujemy żadnego działania.
Przesuwamy iloczyn częściowy o jedno miejsce w prawo.
Przesuwamy mnożnik o jedno miejsce w prawo ( przejście do kolejnego badania bitu mnożnika). Jeżeli badany bit jest bitem znakowym b0, to wtedy gdy jego wartość wynosi 1 odejmujemy mnożną od iloczynu częściowego, zaś gdy jest on równy 0 nie wykonujemy żadnego działania.
Uzyskany iloczyn częściowy przesuwamy o jedno miejsce w lewo (powrót do A), wynik jest w postaci ZU2.
PRZYKŁAD:
Dla II wariantu metody Booth'a
L(A) = = (0.11011)ZM
L(B) = = (1.10101)ZM = (1.01010)ZU1 = (1.01011)ZU2
Przesuwamy mnożną o jedno miejsce w prawo - uzyskanie wartości “A - pół”:
Badamy kolejne bity mnożnika począwszy od ostatniego:
bit = 1 - dodajemy mnożną (“A-pół”) do iloczynu częściowego (na początku równego 0), a następnie przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,
bit = 1 - dodajemy mnożną do iloczynu częściowego, przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,
bit = 0 - nie wykonujemy żadnej operacji, przesuwamy iloczyn częściowy o jedno miejsce w prawo,
bit = 1 - dodajemy mnożną do iloczynu częściowego, przesuwamy otrzymany iloczyn częściowy o jedno miejsce w prawo,
bit = 0 - nie wykonujemy żadnej operacji, przesuwamy iloczyn częściowy o jedno miejsce w prawo,
bit =1 - badany bit jest bitem znakowym i jest równy 1 dlatego wystąpi tzw. poprawka - odejmujemy mnożną od iloczynu częściowego,
. otrzymany wynik przesuwamy o jedno miejsce w lewo.
Wynik: (1.0111001001)ZU2 = (1.1000110111)ZM =
Uwaga:
Mnożymy tylko ułamki!
Jeżeli chcemy pomnożyć ułamki niewłaściwe to zapisujemy je w postaci mantysy i cechy i wykonujemy mnożenie mantys i mnożenie cech, ostateczny wynik to mantysa * cecha.
DZIELENIE LICZB BINARNYCH
Dzielenie można przeprowadzić wykorzystując następujące metody:
metoda porównawcza,
metoda restytucyjna,
metoda nierestytucyjna,
Metoda porównawcza - jest stosowana w zapisie znak moduł (ZM) i gdy jest spełniony warunek A<B, gdzie:
A - dzielna
B - dzielnik
r0 - reszta początkowa
Rn - reszta z dzielenia
rn - n - ta reszta częściowa
Q - iloraz uzyskany w algorytmie o bitach qi.
Metoda ta polega na porównywaniu dzielnika z n - tą resztą.
Jeżeli dzielnik jest mniejszy od rn-tej reszty rn=>B, to odejmujemy dzielnik od przesuniętej n - tej reszty, a bit ilorazu qi = 1.
Jeżeli n - ta reszta jest mniejsza od dzielnika rn<B, to kolejny bit ilorazu qi = 0. Następnie przesuwamy wynik o jedno miejsce w lewo. Otrzymaną resztę częściową porównujemy z dzielnikiem.
Uwaga: Wynikiem dzielenia jest iloraz Q o bitach q0q1..qi.W pierwszym kroku porównujemy resztę początkową r0 z dzielnikiem, gdzie r0 - to L(A) zapisana na tylu pozycjach co L(B).
PRZYKŁAD:
Dla metody porównawczej
A= = (1.0000011)ZM
B = = (0.1001)ZM
Warunek A<B jest spełniony; porównujemy kolejne reszty częściowe z modułem dzielnika:
reszta z dzielenia Rn wyraża się wzorem:
Rn =
Rn = 0.011 * 101.110
Bit znaku q0 = a0 A b0, czyli q0 = 1, bo a0 = 1, b0 = 0
Ostateczny iloraz Q wynosi:
Q = q0 q1 q2...qn
Q = 1.00001
Metoda restytucyjna - to metoda dzielenia dwóch liczb zapisanych w kodzie znak moduł (ZM) i gdy |A|<|B|.
Algorytm metody restytucyjnej różni się od metody porównawczej tym, że zawsze następuje odejmowanie dzielnika od i - tej reszty. Jeżeli otrzymana reszta jest większa od zera, to kolejny bit ilorazu jest równy 1, jeżeli jest mniejsza od zera, to kolejny bit ilorazu jest równy 0. Bez względu na znak reszty z odejmowania przesuwamy resztę o jedno miejsce w lewo. Dla reszty ujemnej z powrotem dodajemy dzielnik, zanim przesuniemy wynik w lewo.
Metoda nierestytucyjna - to metoda dla dzielenia dwóch liczb zapisanych w kodzie ZU2. Dzielna A i dzielnik B są ułamkami w postaci znormalizowanej oraz wymagane jest by był spełniony warunek |A|<|B|.
Metoda ta polega na badaniu znaku dzielnika i kolejnej reszty częściowej. Jeżeli znaki są zgodne to odejmujemy dzielnik od przesuniętej w lewo kolejnej reszty częściowej. Jeżeli znaki ich są różne to dodajemy dzielnik do przesuniętej w lewo kolejnej reszty częściowej. Przy zgodnych bitach znakowych dzielnika i reszty bit ilorazu jest jedynką, a dla znaków przeciwnych jest zerem. Do otrzymanego wyniku dodajemy poprawkę równą: -1+2-n, gdzie n - oznacza n - tą resztę z dzielenia.
PRZYKŁAD:
Dla metody nierestytucyjnej
Warunek lAl < lBl jest spełniony:
Wynik: 0.101;
Do wyniku dodajemy poprawkę, która wynosi:
-1 + 2-n, gdzie n jest to nr ostatniej reszty dzielenia, zatem:
-1 + 2-n = (1.0001)ZU2
Logika binarna
Logika binarna zajmuje się zmiennymi mogącymi przyjmować dwie wartości dyskretne oraz operacjami mającymi znaczenie logiczne. Dwie wartości jakie mogą te zmienne przyjmować noszą przy tym różne nazwy, takie jak: prawdziwy i fałszywy, tak i nie, itd., wygodnym będzie przypisanie im wartości 1 i 0.
Logika binarna używana jest w celu matematycznego opisu przetwarzania informacji binarnej. Jest ona szczególnie dostosowana do analizy i projektowania systemów cyfrowych. Dla przykładu cyfrowe układy logiczne wykonujące binarne operacje arytmetyczne są układami, których zachowanie najwygodniej opisać za pomocą zmiennych binarnych i operacji logicznych. Logika binarna przedstawiona w tym punkcie równoważna jest algebrze zwanej algebrą Boole'a.
Logika binarna zajmuje się zmiennymi binarnymi i operacjami logicznymi. Zmienne oznaczane są literami alfabetu takimi jak: A, B, C, x, y, z, itd. Każda z nich przyjmować może dwie różne wartości: 1 i 0. Istnieją trzy podstawowe operacje logiczne: I, LUB oraz NIE.
Operacja I jest przedstawiana za pomocą kropki (znak mnożenia), którą często pomijamy. Np.: wyrażenie x*y = z lub xy = z. Operacja logiczna I jest rozumiana w ten sposób, że z = 1 wtedy gdy x = 1 i y = 1, w przeciwnym przypadku z = 0 (należy pamiętać, że x, y, z są zmiennymi binarnymi i mogą przyjmować wartości 1 lub 0).
Operacja LUB jest przedstawiana za pomocą znaku + . Np.: x+y = z odczyt x lub y jest równe z, co oznacza, że z = 1 wtedy gdy x = 1 lub y = 1 lub gdy zarówno x = 1 i y = 1, w przypadku gdy x = 0 i y = 0 to z = 0.
Operacja NIE jest przedstawiona za pomocą znaku prim lub kreski. Np.: x' = z odczytujemy: nie x jest równe z
Algebra Boole'a - podstawowe definicje:
Domknięcie - zbiór S jest domknięty ze względu na operator binarny, jeśli dla każdej pary elementów ze zbioru S operator ten określa regułę na podstawie, której otrzymuje się w sposób jednoznaczny element zbioru S. Na przykład zbiór liczb naturalnych N ={1, 2, 3,...} jest domknięty względem operacji dodawania (+), gdyż dla każdego a, b N otrzymujemy w sposób jednoznaczny c N przy pomocy operacji a + b = c. Zbiór liczb naturalnych nie jest domknięty względem operatora binarnego minus (-) oznaczającego arytmetyczne odejmowanie, gdyż np.: 2 -3 = -1, a więc a, b N lecz N. €c
Prawo łączności - mówimy, że operator binarny * na zbiorze S jest łączny gdy (x * y) * z = x * (y * z) dla każdego x, y, z S.
Prawo przemienności - mówimy, że operator binarny * na zbiorze S jest przemienny, gdy x * y = y * x dla każdego x, y S.
Element identycznościowy - zbiór S posiada element identycznościowy względem operacji binarnej * na S, jeśli istnieje element e S o własności e * x = x * e = x dla każdego x S. Np.: Element O jest elementem identycznościowym względem operacji + na zbiorze liczb całkowitych I = {...-3, -2, -1, 0, 1, 2, 3,...} x + 0 = 0 + x = x dla każdego x I
Element odwrotny - zbiór S mający element identycznościowy e względem operatora binarnego * posiada element odwrotny, jeśli dla każdego x S istnieje taki element y S, że x * y = e. Np.: w zbiorze liczb całkowitych elementem odwrotnym do elementu a jest element -a , gdyż a + (-a) = 0.
Prawo rozdzielczości - jeśli * i • są operatorami binarnymi na zbiorze S, mówimy, że operator * jest rozdzielny względem operatora • jeśli zachodzi równość x * (y • z) = (x * y) • (x * z)
Aksjomatyczna definicja algebry Boole'a - postulaty Huntigtona:
1. Domknięcie względem operatora +
2. Domknięcie względem operatora *
3. Element identycznościowy względem + oznaczony jako 0 : x + 0 = 0 + x = x
4. Element identycznościowy względem * oznaczony jako 1 : x * 1 = 1 * x = x
5. Przemienność względem dodawania : x + y = y + x
6. Przemienność względem mnożenia: x * y = y * x
7. Rozdzielność mnożenia względem dodawania: x* (y + z) = (x * y) + (x * z)
8. Rozdzielność dodawania względem mnożenia: x + (y * z) = (x + y) * (x + z)
9. Dla każdego elementu x B istnieje taki element x' B, że: x + x' = 1 oraz x* x' = 0
10. Istnieją przynajmniej dwa elementy x, y B takie, że x y.
Algebra Boole'a dwuwartościowa:
Dwuelementowa algebra Boole'a jest określona na zbiorze dwóch elementów B={0, 1}, przy czym reguły dla operatorów binarnych + i * podano w następujących tabelach:
Operacja I:
x y x * y
0 0 0
0 1 0
1 0 0
1 1 1
Operacja LUB:
x y x + y
0 0 0
0 1 1
1 0 1
1 1 1
Operacja NIE:
x x'
0 1
1 0
Powyższe reguły są dokładnie takie same jak operacje: I, LUB, NIE.
Należy teraz pokazać, że postulaty Huntingtona są spełnione dla zbioru b = {0, 1} oraz dwóch operatorów binarnych zdefiniowanych powyżej:
Domknięcie - zachodzi, gdyż jak widać bezpośrednio z tablic, wynikiem każdej operacji jest 1 lub 0, a 1.0 B.
Z tablic wynika, że:
0 + 0 = 0 0 + 1 = 1 + 0 = 1
1 * 1 = 1 1 * 0 = 0 * 1 = 0
co określa dwa elementy identycznościowe 0 dla + i 1 dla * - zgodnie z postulatem 2.
Przemienność - wynika z symetrii tablic obu operatorów binarnych.
Prawo rozdzielności:
rozdzielność mnożenia względem dodawania - można udowodnić na podstawie tabeli prawdy,
rozdzielność dodawania względem mnożenia - można również 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
co sprawdza postulat 5.
Postulat 6 jest spełniony gdyż dwuelementowa algebra Boole'a posiada dwa różne elementy 1 i 0 przy czym 1 0.
Podstawowe twierdzenia i własności algebry Boole'a:
Dualność - postulaty Huntingtona zostały zgrupowane parami i oznaczone jako część a) i część b). Jedna część postulatów może być otrzymana z drugiej, jeśli zamieni się miejscami operatory binarne oraz elementy identycznościowe. Ta własność algebry Boole'a zwana jest zasadą dualności. Głosi ona, że każde wyrażenie algebraiczne jakie wyprowadzić można na podstawie postulatów algebry Boole'a pozostaje słuszne, jeśli operatory i elementy identycznościowe zostaną zamienione miejscami. W dwuelementowej algebrze Boole'a elementy identycznościowe i elementy zbioru B są te same: 1 i 0. Zasada dualności posiada wiele zastosowań, aby otrzymać wyrażenie dualne do danego wyrażenia algebraicznego należy zamienić miejscami operatory LUB oraz I, a 1 zastąpić 0, bądź odwrotnie
Zestawienie:
Postulat 2 a) x + 0 = x b) x * 1 = x
Postulat 5 a) x + x' = 1 b) x * x' = 0
Twierdzenie 1 a) x + x = x b) x * x = x
Twierdzenie 2 a) x + 1 = 1 b) x * 0 = 0
Twierdzenie 3 - INWOLUCJA (x')' = x -----------------
Postulat 3 - PRZEMIENNOŚĆ a) x + y = y + x b) x * y = y * x
Twierdzenie 4 - ŁĄCZNOŚĆ a) x +(y + z) = (x + y) + z b) x *(y * z) = (x * y)* z
Postulat 4 - ROZDZIELNOŚĆ a) x *(y + z) = x * y + x * z b) x +y * z = (x + y) * (x + z)
Twierdzenie 5 - PRAWA DE MORGANA a) (x + y)' = x' * y' b) (x * y)' = x' + y'
Twierdzenie 6 - ABSORPCJA a) x + x * y = x b) x *(x + y) = x
Funkcje Boolowskie:
Zmienna binarna może przyjmować wartości 0 lub 1. Funkcja boolowska jest to wyrażenie utworzone przy pomocy zmiennych binarnych dwu operatorów binarnych I oraz LUB, operatora jednoargumentowego NIE, nawiasów i znaku równości. Dla zadanych wartości zmiennych funkcja taka przyjmować może wartości: 0 lub 1.
Na przykład:
Weźmy funkcję: F1 = xyz'
Funkcja F1 równa jest 1 jeśli x = 1 i y = 1 i z = 0, w innych przypadkach F1 = 0.
Każda funkcja boolowska może być przedstawiona za pomocą tablicy prawdy. Liczba wierszy w tej tablicy wynosi 2n, gdzie n jest liczbą zmiennych. Kombinację zer i jedynek występującą w każdym wierszu łatwo 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.
Gdy dwie zmienne połączone są ze sobą przy pomocy operatorów binarnych I oraz LUB, tworzą one odpowiednio funkcje boolowskie x * y i x + y. Jak stwierdzono istnieje 22n funkcji n zmiennych. Dla dwóch zmiennych x i y istnieje 16 możliwych do utworzenia funkcji.
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 / /
+
`
`
LEGENDA:
/ - ZAKAZ
- ALBO
+ - LUB
- NOR
- RÓWNOWAŻNOŚĆ
` - NEGACJA
- IMPLIKACJA
- IMPLIKACJA
- NAND
F0 = 0 ZERO
F1 = x * y i - x i y
F2 = x * y' = x / y ZAKAZ - x lecz nie y
F3 = x Funkcja jest równa x
F4 = x' * y = y / x ZAKAZ - y lecz nie x
F5 = y Funkcja jest równa y
F6 = x' * y + x * y' = x y
ALBO - x lub y, lecz nie oba
F7 = x + y LUB - x lub y
F8 = (x + y)' = x y
NOR - nie lub
F9 = x' * y' + x * y = x y
RÓWNOWAŻNOŚĆ - x równoważne y
F10 = y' NEGACJA - nie y
F11 = x + y' = x y
IMPLIKACJA - jeśli y to x
F12 = x' NEGACJA - nie x
F13 = x' + y = x y
IMPLIKACJA - jeśli x to y
F14 = (x * y)' = x y
NAND -nie i
F15 = 1 JEDEN, IDENTYCZNOŚĆ
ZASADY AUTOMATYCZNEJ TRANSLACJI
Translacja i translatory
Zagadnienia budowy translatorów, jak i samego procesu translacji stanowią jeden z najrozleglejszych działów informatyki, któremu możnaby poświęcić odrębną pracę, toteż niniejsze rozważania mają na celu zaznaczenie pewnych pojęć z tego zakresu, skupiając się głównie na procesie translacji wyrażeń do postaci ONP. Głównym źródłem informacji wykorzystanym dla tego rozdziału jest pozycja: W. M.Turskiego [TURS 77].
Języki programowania niskiego czy też wysokiego poziomu mają na zadanie przetworzyć ogół algorytmów w nich zapisanych na taką postać aby maszyna cyfrowa była w stanie je wykonać tzn. dać takie efekty jakie programista zakłada tworząc dany program. Między tymi językami występuje jednak zasadnicza różnica : program zapisany w języku niskiego poziomu (w języku wewnętrznym) stanowi ciąg instrukcji dostępnych przez dany procesor czy też maszynę cyfrową i jest wykonywany bezpośrednio; natomiast program zapisany w językach wysokiego poziomu takich jak Pascal czy C ( w językach zewnętrznych) wymaga dodatkowo przetłumaczenia na ciąg instrukcji dostępnych przez maszynę która ma dany program wykonać. Owo tłumaczenie w pewnym stopniu przypomina tłumaczenie języków etnicznych, przy uwzględnieniu dodatkowych warunków jak: znajomość kultury, tradycji i historii danego języka. Podobnie tłumacząc programy zewnętrzne na wewnętrzne należy także uwzględnić dodatkowe elementy takie jak dane wejściowe do programu, które także muszą być przetłumaczone do tego stopnia aby spodziewany efekt końcowy programu zapisanego w języku zewnętrznym niczym się nie różnił od efektu działania samej maszyny.
Proces przekładu tekstów zapisanych w jednym języku na drugi nosi nazwę translacji. W przypadku gdy dany język wysokiego poziomu ma stosunkowo łatwą gramatykę, translacja może być wykonana samoczynnie przez maszynę cyfrową przy pomocy specjalnego programu translacji zwanego translatorem.
Wykorzystując translatory programiści mogą posługiwać się zewnętrznymi językami programowania, co znacznie ułatwia tworzenie oprogramowania, gdyż czas stracony na żmudnym pisaniu instrukcji w języku wewnętrznym zostaje ograniczony do wybrania odpowiednich procedur i funkcji z repertuaru danego języka wysokiego poziomu, a sam programista może skupić się na rozwiązywaniu powstałych problemów implementacyjnych.
Translatory dzielimy zazwyczaj na dwie kategorie: kompilatory i interpretatory. Podział ten bardzo często nie ma miejsca w praktyce, gdyż buduje się translatory wykazujące jednocześnie cechy kompilatorów i interpretatorów.
Najogólniej, kompilator jest translatorem, operującym na całym tekście programu źródłowego generując tekst przekładu jako całość, podczas gdy interpreter operuje na poszczególnych jednostkach syntaktycznych programu źródłowego i generuje ich przekłady. Jeśli więc wykonywamy program początkowo zapisany w języku zewnętrznym to:
• używając kompilatora, możemy przystąpić do wykonania programu w postaci docelowej dopiero po zakończeniu translacji. Oznacza to, że uzyskany tekst będący przekładem tekstu źródłowego w całości wprowadzany jest do maszyny cyfrowej;
• używając interpretatora, możemy wykonywać przekłady poszczególnych jednostek syntaktycznych, nie czekając na cały proces translacji. Oznacza to, że cały czas operujemy na tekście źródłowym tłumacząc tylko te jednostki syntaktyczne, które są potrzebne aby poszczególny fragment programu mógł zadziałać.
W praktyce rzadko dokonuje się bezpośredniej translacji programów z języka zewnętrznego na język maszynowy. Najczęściej stosuje się proces pośredni to znaczy, najpierw dokonuje się translacji z języka zewnętrznego na język asemblerowy, a potem z języka asemblerowego na język maszynowy. Zastosowanie takiej dwuetapowej translacji niesie za sobą wiele zalet, a główna z nich jest możliwość łączenia poszczególnych części programów zapisanych w różnych językach zewnętrznych.
Stos i odwrotna notacja polska (ONP)
Bardzo ważnymi pojęciami bez których trudne byłoby zrozumienie zasad jakiejkolwiek translacji są : stos i odwrotna notacja polska (ONP).
STOS- jest to organizacja sekwencyjna pamięci operacyjnej maszyny cyfrowej. Stos działa jak pojemnik określonych jednostek, przy czym pobieranie elementów w nim zgromadzonych odbywa się w kolejności odwrotnej do magazynowania. Jest to tak zwana struktura LIFO (last-in-first-out co oznacza „ ten co ostatni przyszedł pierwszy odchodzi”). Dla stosu określa się dwie podstawowe operacje:
• dos(a)- dopisz na stosie - w wyniku wykonania tej operacji jednostka a zostaje umieszczona na szczycie stosu (staje się pierwszym elementem stosu)
• ods(a)- odczytaj ze stosu - w wyniku wykonania tej operacji jednostka a zostaje wydana na zewnątrz stosu.
ODWROTNA NOTACJA POLSKA (ONP)- mianem tym obdarzono jeden z wariantów beznawiasowego zapisu wyrażeń formalnych, wynalezionego przez polskiego logika Jana Łukasiewicza (1878-1956). W tym beznawiasowym zapisie symbole operandów poprzedzają bezpośrednio symbol operatora, na przykład wyrażenie a+b zapisujemy w ONP jako a b +.
Translacja wyrażeń arytmetycznych
Współczesne podejście translacji wyrażeń arytmetycznych polega na wydzieleniu dwu etapów translacji:
• translacja do ONP
• translacja ONP na język symboliczny
W celu zobrazowania translacji do ONP przyjmujemy, że źródłowy zapis wyrażeń arytmetycznych pojawia się na wejściu specjalnego automatu (Rys.1). Na wyjściu uzyskamy zapis ONP tych wyrażeń, sam zaś automat wyposażony jest w pamięć stosową.:
wyrażenie Automat ze stosem ONP wyrażenia
arytmetyczne arytmetycznego
Rys. 1. Model automatu ze stosem do translacji wyrażeń arytmetycznych
Podczas translacji wyrażeń arytmetycznych szczególnej analizie poddawane są symbole operacji (+,-,*,itp.) zwane ogranicznikami ,stąd wprowadza się dodatkowo listę priorytetów ograniczników (Tab.1):
Ogranicznik Priorytet
+ - 0
1÷* /
↑ 2
Tab.1.Priorytety symbolów operacji (ograniczników)
Działanie automatu odbywa się według następującego algorytmu postępowania:
1. Pobierz kolejny element (nazwę zmiennej, stałą lub ogranicznik) źródłowego wyrażenia arytmetycznego.
2. Jeśli ten element jest nazwą zmiennej lub stałą, przekaż go natychmiast na wyjście; w przeciwnym wypadku, jeśli priorytet ogranicznika jest wyższy od priorytetu ogranicznika zajmującego szczyt stosu lub jeśli stos jest pusty, dopisz go na stos, jeśli wreszcie na szczycie stosu znajduje się ogranicznik o wyższym lub równym priorytecie - odczytaj go ze stosu i prześlij na wyjście, a ogranicznik z wejścia dopisz na stosie, chyba, że nowy ogranicznik zajmujący szczyt stosu w wyniku odczytania priorytetu ma priorytet nie mniejszy niż ogranicznik z wejścia. w takim przypadku należy kontynuować odczytywanie ze stosu i przesyłanie na wyjście aż do wystąpienia na szczycie stosu ogranicznika o priorytecie niższym od priorytetu ogranicznika nadchodzącego z wejścia.
3. Jeśli wyrażenie źródłowe zostało wyczerpane, odczytaj wszystkie ograniczniki ze stosu na wyjście automatu.
Przykład 1 przedstawia poszczególne takty procesu translacji do ONP dla wybranego wyrażenia arytmetycznego.
Przykład 1:
k÷Niech wyrażenie źródłowe ma postać: x + 3 * z
Poszczególne takty translacji są następujące:
Takt Wejście Stos Wyjście
1 x x
2 + +
3 3 + 3
4 * +,*
5 z +,* z
*÷ +,÷6
k÷7 k +,
8 koniec ,+÷
Rys.2. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 1
, +÷Na wyjściu uzyskamy wyrażenie ONP postaci: x, 3, z, *, k,
Dla uzyskania prawidłowej konwersji wyrażeń arytmetycznych uzupełniamy listę ograniczników o następujące symbole:
• nawiasy ( )
• operator negacji NEG (jako symbol operacji unarnej służący do zmiany znaku)
• funkcje trygonometryczne (operatory jednoargumentowe)
Priorytety wyżej wymienionych ograniczników przedstawia tabela 2
Ogranicznik Priorytet
( 0
+ - ) 1
NEG 2÷* /
3↑
sin cos tg ctg 4
Tab.2. Priorytety rozszerzonych symbolów operacji (ograniczników)
Działanie automatu uzupełniamy następującymi regułami:
1. Ogranicznik „(” jest dopisywany do stosu bez jakiegokolwiek odczytywania stosu.
2. Ogranicznik „)” nie jest dopisywany na stos, pojawienie się jednak tego ogranicznika na wejściu powoduje odczytanie ze stosu i przesłanie na wyjście wszystkich kolejnych ograniczników aż do pojawienia się ogranicznika „(”.
3. Ogranicznik „(” ze szczytu stosu zostaje usunięty bez przekazywania na wyjście, jeśli aktualnym symbolem na wejściu jest „)”.
Pojawienie się nawiasu zamykającego „)” na wejściu automatu powoduje wyprowadzenie na wejście wszystkich ograniczników z wnętrza pary nawiasów aż do nawiasu otwierającego „(” oraz likwidację tego nawiasu.
Przykład 2 przedstawia proces translacji z uwzględnieniem powyższych reguł:
Przykład 2:
( d - e*k )↑Niech wyrażenie źródłowe ma postać: b * c
Poszczególne takty translacji są następujące:
Takt Wejście Stos Wyjście
1 b b
2 * *
3 c * c
↑ *,↑4
,(↑5 ( *,
,( d↑6 d *,
,(,-↑7 - *,
8 e ,(,- e↑*,
,(,-,*↑9 * *,
,(,-,* k↑10 k *,
*,-↑11 ) *,
12 koniec ,*↑
Rys.3. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 2
↑Na wyjściu uzyskamy wyrażenie ONP postaci: b, c, d, e, k, *, -, ,*
Przykład 3 przedstawia translację krótkiego wyrażenia arytmetycznego z funkcjami trygonometrycznymi.
Przykład 3:
Niech wyrażenie źródłowe ma postać: sinx + cosy + tgz
Poszczególne takty translacji są następujące:
Takt Wejście Stos Wyjście
1 sin sin
2 x sin x
3 + + sin
4 cos +, cos
5 y +, cos y
6 + + cos, +
7 tg +, tg
8 z +, tg z
9 koniec tg, +
Rys.4. Poszczególne takty procesu translacji wyrażenia do ONP dla przykładu 3
Na wyjściu uzyskamy wyrażenie ONP postaci: x , sin, y, cos, +, z, tg, + ,
Nic nie stoi na przeszkodzie by procesowi translacji poddać wyrażenia arytmetyczne zawierające operacje logiczne i warunkowe. W tym celu należy odpowiednio rozszerzyć ilość priorytetów, a także chcąc odzwierciedlić składnie: if..then..else należy wprowadzić odpowiednie oznaczenia, które będą sygnalizowały konieczność wykonania skoku warunkowego lub bezwarunkowego. Operacje te zapisujemy w postaci SW (k) i SB (k), gdzie SW- oznacza then, a SB else. Dla translacji wyrażeń arytmetycznych z elementami logicznymi koniecznym jest wprowadzenie dwóch różnych pojęć priorytetów: priorytet porównawczy (p.p) i priorytet stosowy (p.s.). gdzie: priorytet porównawczy dla danego ogranicznika oznacza moc rozładowania stosu, a priorytet stosowy moc blokowania stosu. W praktyce oznacza to, że jeżeli na wejściu automatu pojawi się symbol operacji (ogranicznik) to celem ewentualnego odczytania symboli ze stosu porównujemy priorytet porównawczy tego symbolu z priorytetem stosowym symboli operacji na stosie.
Uzupełniona tablica priorytetów ograniczników wraz z uwzględnieniem pojęć: priorytet stosowy i porównawczy kształtuje się następująco:
Ogranicznik p. stosowy p. porównawczy
(, if 0 nie dotyczy
then 0 1
else 1 2
), ; nie dotyczy 1
3 3≡
4 4⊃
5 5∧
6 6∨
- 7 7
> ≤ ≥ < 8 8≠=
+- 9 9
NEG 10 10÷* /
11 11↑
Tab.3. Uzupełniona lista ograniczników z uwzględnieniem elementów logicznych
Algorytm konwersji zostaje uzupełniony o nowe reguły związane z elementami logicznymi: if..then...else:
1. Gdy na wejściu pojawi się ogranicznik „then”, wówczas, oprócz wszystkich ograniczników wyprowadzanych ze stosu na wyjście ze względu na ich priorytety, zostaje także usunięty ze szczytu stosu ogranicznik „if” ( konstrukcja if - then jest analogiczna do pary nawiasów ( ) w wyrażeniach arytmetycznych). Na wyjście automatu zostaje wyprowadzona operacja SW z pustym nawiasem SW( ), zaś ogranicznik „then” zostaje dopisany do stosu wraz z numerem, pod jakim występuje w zapisie ONP operacja SW( ).
2. Gdy na wejściu pojawia się ogranicznik „else”, powoduje on wyprowadzenie wszystkich symboli na wyjście automatu aż do momentu pojawienia się ma stosie ogranicznika „then”. Na wyjście zostaje wpisana niekompletna operacja SB(), operacja SW( ) będąca na wyjściu zostaje uzupełniona przez wpisanie do nawiasu numeru pozycyjnego z zapisu ONP, a sam ogranicznik „else” zostaje dopisany do stosu wraz z numerem pozycyjnym SB( ) w zapisie ONP.
3. Gdy podczas wyprowadzania ograniczników ze stosu natrafimy na „else”, wówczas uzupełniamy odpowiedni nawias operacji SB( ) odpowiadającej danemu „else”, zaś sam ogranicznik else zostaje zlikwidowany tzn. nie jest wyprowadzany na wyjście automatu.
Przykład 4 obrazuje translację wyrażeń zawierających elementy logiczne.
Przykład 4:
Niech wyrażenie na wejściu ma postać: y + ( if a>0 then 3 else a )
Poszczególne takty konwersji przedstawia rysunek 5.
Takt Wejście Stos Wyjście Numer pozycyjny w ONP
1 y y 1
2 +9 +9
3 ( +9 (0
4 if +9 (0 if0
5 a +9 (0 if0 a 2
6 >8 +9 (0 if0 >8
7 0 +9 (0 if0 >8 0 3
8 then1 +9 (0 then50 >
SW()
po takcie 10 - SW(8) 4
5
9 3 +9 (0 then50 3 6
10 else2 +9 (0 else71 SB()
po takcie 12- SB(9) 7
11 a +9 (0 else71 a 8
12 )1 +9
13 ; + 9
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.
Rys.5. Poszczególne takty konwersji dla przykładu 4
Etap drugi translacji wyrażeń arytmetycznych polega na wygenerowaniu programu w języku symbolicznym (docelowym). Proces ten także korzysta z pamięci stosowej a sam algorytm postępowania wymaga przyjęcia pewnych oznaczeń :
i - i=0,1,.... są to kolejne pozycje stosu; język docelowyδ i+1 gdzieδi op δi : = δi := Z i δpozwala na występowanie dwu typów instrukcji: Z jest nazwą zmiennej lub stałą, a op jest symbolem operacji.
Proces translacji zapisu ONP na język docelowy przebiega według następującego algorytmu:
1. Ustalamy i=0, k=1
2. Odczytujemy k-ty element ONP : Ek
3. i:=Ek i następujeδJeśli Ek jest nazwą zmiennej lub stała, generuje się operacja NEG, generuje≠ i:= i +1; jeśli Ek jest symbolem operacji op →zwiększenie i o 1 i := i -→i-1 oraz następuje zmniejszenie i o 1 δi-2 op δi-2 := δsię operacja i-1δi-1 := - δ1; jeśli Ek = NEG, następuje wygenerowanie operacji
4. Jeśli Ek nie był ostatnim symbolem wyrażenia w ONP, to k:= k + 1 i przechodzimy do punktu 2.
Sposób translacji wyrażenia ONP na język symboliczny przedstawia przykład 5.
Przykład 5:
Niech wyrażenie arytmetyczne ma postać: ( a + b ) (-c) )↑/ ( k
Postać ONP tego wyrażenia jest następująca: a, b, +, k, c, /↑NEG,
i k
0 1
0:= a 1 2δ1:
i:= b 2 3δ2:
i 1δ0 +δ0:= δ3: 4
i:= k 2 5δ4:
2:= c 3 6δ5:
2 3 7δ2:= -δ6:
2 2δ ↑i δi:= δ7: 8
1 1 9δo / δ0:= δ8:
9: brak symboli w wyrażeniu ONP -koniec algorytmu.
Wiadomości zawarte w tym rozdziale przedstawiają nam drogę od zrodzenia się algorytmu, aż po wykonanie programu na maszynie cyfrowej co schematycznie przestawia rysunek 6
algorytm programowanie program w języku
wysokiego poziomu
kod maszynowy program w języku kompilacja
asemblerowym
Wykonanie na
komputerze
Rys.6. Schematyczny przebieg powstania programu
AUTOMAT SKOŃCZONY
Deterministyczny automat skończony
W tym rozdziale tematem rozważań będą zagadnienia z dziedziny automatów skończonych i wyrażeń regularnych. Głównym źródłem wiadomości teoretycznych przedstawionych w tym rozdziale jest praca J.E.Hopcrofta i J.D.Ullmana [HOPC 94].
Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach. System taki w danej chwili może znajdować się w jednym ze skończonej liczby stanów, który to stan jest ściśle uzależniony od stanu poprzedniego. Jeden ze stanów pełni rolę stanu początkowego, od którego dany automat rozpoczyna działanie, z drugiej strony niektóre stany pełnią rolę stanów końcowych kończąc pracę automatu. Praca automatu oparta jest na analizie symboli wejściowych ze skończonego alfabetu. Każdy odczytany symbol wymusza przejście do innego stanu ( w niektórych przypadkach przejście prowadzi do tego samego stanu). Po przeanalizowaniu wszystkich symboli automat skończony może przyjąć jeden z dwu stanów: akceptacji lub nieakceptacji. Bardzo często automat skończony, który w dalszych rozważaniach będziemy oznaczać jako AS jest przedstawiany za pomocą grafów skierowanych, w których wierzchołki obrazują stany automatu. Jeżeli istnieje przejście z jednego stanu do następnego to takie przejście przedstawione jest za pomocą łuku. Dla wyodrębnienia stanu początkowego, wierzchołek rozpoczynający pracę automatu wzbogacony jest o strzałkę z napisem START. W celu zaakcentowania stanu końcowego wprowadza się dwa odrębne wierzchołki grafu opatrzone etykietą A (s. akceptacji) N (s. nieakceptacji), bądź stan końcowy oznacza się podwójnym kółkiem. Rysunek 7 przedstawia fragment grafu dla automatu skończonego:
start q0 q1 q4
q2 q3
Rys. 7. Fragment grafu przejść dla automatu skończonego
Automat skończony przedstawiamy formalnie jako uporządkowaną piątkę:
< , qo, Fδ, ΣQ, >
gdzie:
Q - jest skończonym zbiorem stanów,
- jest skończonym alfabetem symboli wejściowych, q0Σ należące do Q jest stanem początkowym od którego automat rozpoczyna działanie,
Q - jest zbiorem stanów końcowych (stan akceptacji lub nieakceptacji),⊆F
określa każdemu stanowi q iδ w Q czyli Σ - jest funkcją odwzorowującą Q x δ każdemu symbolowi na wejściu nowy stan automatu.
Automat skończony możemy sobie wyobrazić jako głowicę sterująco-czytającą, która analizuje symbole zapisane na taśmie w sposób pokazany na rysunku 8.
głowica
sterująco-
czytająca
Rys. 8. Schemat pracy automatu skończonego
W danej chwili automat odczytuje symbol wejściowy i przechodzi do kolejnego stanu. Jeżeli stan ten jest stanem akceptacji to znaczy, że dotychczasowy ciąg symboli na taśmie jest zaakceptowany przez AS. Jeżeli głowica przesunęła się na koniec taśmy, a ostatni stan jest stanem zaakceptowanym przez AS to AS zaakceptował cały łańcuch.
Formalnie przyjmuje (qo,x)= p dlaδsię, że łańcuch jest akceptowany przez automat M, jeżeli jakiegoś p należącego do F. Język akceptowany przez dany automat M oznaczany L(M), to zbiór {x | (qo,x) należy do F}. Język nazywamy zbiorem regularnym, jeżeli jest on językiem akceptowanym przez pewien automat skończony. Zbiory regularne zostaną szczegółowo omówione pod koniec tego rozdziału.
W celu zobrazowania konstrukcji automatu skończonego przeanalizujmy dwa przykłady dotyczące akceptacji liczb podzielnych przez wybraną liczbę.
Przykład 6. Automat skończony akceptujący liczby podzielne przez 2
Dla tego automatu =Σzbiór symboli wejściowych będzie złożony z cyfr od 0..9 czyli {0,1,2,3,4,5,6,7,8,9}. Wiadomo też, że liczba jest parzysta gdy ostatnia jej cyfra jest podzielna bez reszty przez 2.
• Konstrukcję automatu rozpoczynamy od wykreślenia wierzchołka stanu q0, który jest stanem wejściowym (Rys. 8 )
• Jeżeli pojawi się na wejściu cyfra podzielna przez 2 to zaznaczmy to na grafie jako przejście do stanu q1, jeżeli pojawi się na wejściu cyfra niepodzielna przez 2 to zaznaczmy to jako przejście do stanu q2 (Rys.9)
• jeżeli AS jest w stanie q1 i kolejna cyfra na wejściu jest podzielna przez dwa to automat pozostaje nadal w tym samym stanie co zaznaczamy na grafie łukiem wychodzącym z stanu q1 opatrzonego etykietą {0,2,4,6,8}, jeżeli pozostając w stanie q2 AS lub #φodczyta wszystkie symbole (co umownie oznaczamy pojawieniem się symbolu ) wówczas AS przechodzi do stanu akceptacji A (Rys 10)
• jeżeli AS jest w stanie q1 i kolejna cyfra na wejściu jest nieparzysta to AS pozostaje nadal w tym samym stanie co zaznaczamy na grafie łukiem wychodzącym i wchodzącym do stanu q2 opatrzonego etykietą {1,3,5,7,9}, jeżeli pozostając w stanie q2 AS odczyta wszystkie symbole to wówczas AS przechodzi do stanu nieakceptacji N (Rys. 11 )
• Oczywiście istnieje możliwość pojawienia się na wejściu przemiennie liczb parzystych i nieparzystych a tym samym przejścia z stanu q1 do stanu q2 (Rys 12 - ostateczna konstrukcja automatu )
start q0
Rys. 8
{0,2,4,6,8} q1
start q0
{1,3,5,7,9} q2
Rys. 9
{0,2,4,6,8}
Aφ
{0,2,4,6,8} q1
start q0
{1,3,5,7,9} q2
Rys. 10
{0,2,4,6,8}
Aφ
{0,2,4,6,8} q1
start q0
φ{1,3,5,7,9} q2
N
{1,3,5,7,9}
Rys.11
{0,2,4,6,8}
Aφ
{0,2,4,6,8} q1
start q0 { 1,3,5,7,9} { 0, 2,4,6,8}
φ{1,3,5,7,9} q2
N
{1,3,5,7,9}
Rys. 8-12. Konstrukcja automatu skończonego akceptującego liczby podzielne przez 2
Pojawienie się na wejściu liczby np.123 dla rozpatrywanego automatu sprawi, że automat przejdzie przez następujący porządek stanów: q0, q2, q1, q2, N - czyli liczba 123 nie zostanie zaakceptowana przez automat ( co jest zgodne z prawda gdyż 123 nie jest liczbą parzystą); natomiast pojawienie się liczby 36 wymusi przejście przez stany: q0, q2, q1, A-czyli liczba zostanie zaakceptowana prze automat (co jest zgodne z prawdą gdyż 36 - jest liczbą parzystą).
Przykład 7. Automat skończony akceptujący liczby podzielne przez 3.
Dla tego automatu zbiór symboli = {0,1,2,3,4,5,6,7,8,9}.Σwejściowych będzie złożony z cyfr od 0..9 czyli Wiadomo też, że liczba jest podzielna bez reszty przez 3 gdy suma cyfr danej liczby jest podzielna przez 3. Musimy więc rozpatrzyć następujące przypadki tego zadania: po pierwsze jeżeli liczba złożona jest z cyfr 0,3,6,9 to jest ona na pewno podzielna przez 3. Dla cyfr 1,4,7 i 2,5,8 rozpatrza się dodatkowe warunki : pojawienie się cyfr 1,4,7 musi wystąpić trzykrotnie bądź musi wystąpić cyfra 2,5,8 by liczba była podzielna przez 3. Tak samo pojawienie się cyfr 2,5,8 musi wystąpić trzykrotnie bądź po pojawieniu się jednej z nich musi wystąpić cyfra 1,4,7. Diagram przejść takiego automatu przedstawia rysunek 13.
{0,3,6,9}
φ
q1 N
{1,4,7}
{0,3,6,9}
{2,5,8}
qo {1,4,7} {2,5,8}
Start {2,5,8}
φ
φA {1,4,7}
q2 N
{0,3,6,9}
Rys. 13. Automat skończony akceptujący liczby podzielne przez 3
Pojawienie się na wejściu liczby 126 spowoduje przejście automatu przez stany: q0, q1, q2, A czyli cyfra jest podzielna przez trzy, natomiast 125 wymusi drogę: q0, q1, q2, N czyli liczba nie jest podzielna przez 3.
W praktyce badanie czy dana liczba jest podzielna przez n sprowadza się do operacji modulo (badanie reszty z dzielenia liczby przez n). W tym celu przed wykreśleniem grafu automatu skończonego tworzymy tabelę stanów, obrazującą przejścia między stanami w zależności od rozpatrywanej cyfry. Tabelę taką tworzymy w następujący sposób:
• liczba kolumn jest równa n, czyli liczbie przez którą dana liczba wejściowa ma być podzielna,
• natomiast liczba wierszy jest równa liczbie cyfr (0-9) uzupełniona o 1 dla symbolu pustego .φ
Przeanalizujmy tabelę 4, która dotyczy automatu skończonego badającego czy liczba jest podzielna przez 3.
q1 q2 q3
T N Nφ
0 q1 q2 q3
1 q2 q3 q1
2 q3 q1 q2
3 q1 q2 q3
4 q2 q3 q1
5 q3 q1 q2
6 q1 q2 q3
7 q2 q3 q1
8 q3 q1 q2
9 q1 q2 q3
Tab.4.Tabela stanów dla automatu skończonego akceptującego liczby podzielne przez 3
Chcąc stworzyć automat skończony badający podzielność liczb przez 4, do tabeli 4 dodajemy jedną kolumnę z stanem q4, zaś samo liczenie w pionie zwiększamy do 4, czyli pierwsza kolumna będzie miała następujący porządek stanów: q1, q2, q3, q4, q1, q2, q3, q4, q1, q2. Na tej podstawie możemy stworzyć automat badający podzielność przez dowolną liczbę.
Dla tego typu automatów pojawienie się na wejściu jakiegokolwiek symbolu powoduje ruch automatu ściśle określoną drogą bez możliwości wyboru. Jak się okaże w kolejnych podrozdziałach wybór drogi automatu wcale nie musi być z góry określony tzn. że dany symbol wejściowy może wymusić przejście do różnych stanów. Dlatego automaty skończone gdzie istnieje tylko jedna droga przejścia ze stanu do stanu dla danego symbolu wejściowego określa się jako deterministyczne automaty skończone (DAS).
Niedeterministyczny automat skończony
Jak już zostało wspomniane w końcówce poprzedniego podrozdziału dany symbol wejściowy może wymusić przejście do różnych stanów, stąd wprowadźmy modyfikację modelu automatu skończonego, polegającą na istnieniu kilku przejść ze stanu przy tym samym symbolu wejściowym. Taka modyfikacja pozwala zdefiniować model niedeterministycznego automatu skończonego (NAS), który formalnie jest definiowany jako uporządkowana piątka:
<, qo, Fδ, ΣQ, >
gdzie:
Q - jest skończonym zbiorem stanów,
- jest skończonym alfabetem symboliΣ wejściowych, q0 należące do Q jest stanem początkowym od którego automat rozpoczyna działanie,
Q - jest zbiorem stanów końcowych (stan akceptacji⊆F lub nieakceptacji),
w 2Q. (2Q - jest zbioremΣ- jest odwzorowaniem Q x δ (q,a) jest zbioremδpotęgowym Q, czyli zbiorem wszystkich podzbiorów Q), czyli wszystkich stanów p, dla których istnieje przejście ze stanu q do p o etykiecie związanej z symbolem wejściowym a.
Rysunek 14 przedstawia konstrukcję NAS akceptującego ciągi zerojedynkowe w których przynajmniej raz wystąpiło podwojenie zer lub jedynek:
1 1
0 0 0 0
start q0 q3 q4
1
q1
1
q2
0
1
Rys.14. Niedeterministyczny automat skończony akceptujący ciągi, w których wystąpiło podwojenie zer lub jedynek.
Z rysunku 14 widać, że ze stanu q0 wychodzą dwie krawędzie (drogi) o etykiecie 0, czyli z chwilą pojawienia się zera na wejściu istnieje możliwość przejścia ze stanu q0 do stanu q1 lub q3 . Taka właśnie możliwość wyboru stanów przy tym samym symbolu wejściowym wyróżnia NAS od DAS. Ten typ automatów będzie akceptował ciąg symboli a1,a2...an, dla którego istnieje ciąg przejść prowadzący od stanu początkowego do stanu końcowego. Dla przykładu ciąg 101001 zostanie zaakceptowany przez powyższy NAS bo istnieje towarzyszący mu ciąg przejść: q0, q0, q0, q3, q4, q4; natomiast dla ciągu 10101 nie istnieje żadne przejście ze stanu początkowego do końcowego, gdyż automat w wyniku pojawienia się symboli 10101 pozostanie w stanie q0 czyli wyrażenie nie zostanie zaakceptowane.
Rysunek 15 przedstawia jeszcze jeden niedeterministyczny automat skończony, który akceptuje ciągi wyrazowe w których wystąpiła przynajmniej raz sekwencja symboli a b c.
{ dowolny symbol }
{ dowolny symbol }
{ w tym a i b } b c
q1 q2 q3
a
Start q0
Rys. 15. NAS akceptujący ciąg symboli, w których przynajmniej raz wystąpiła sekwencja a,b,c
Deterministyczny automat skończony z poprzedniego podrozdziału jest szczególnym przypadkiem NAS, w którym dla każdego stanu istnieje dokładnie jedno przejście ze stanu do stanu czyli każdy DAS jest NAS.
Automat skończony z -ruchamiε
Modyfikacją niedeterministycznego automatu skończonego jest - ruchami. Model automatu w tym przypadku dopuszczaεautomat skończony z . Formalnie niedeterministycznyεprzejście ze stanu do stanu przy pustym wejściu -ruchami jest definiowany jako uporządkowana piątka:εautomat skończony z
< , qo, Fδ, ΣQ, >
gdzie:
, qo, F- takie same znaczenie jak wΣQ, przypadku DAS i NAS
jest zbioremδ}) w 2Q. Czyli ε{∪ Σ- odwzorowuje Q x (δ wszystkich stanów p takich, że istnieje przejście o etykiecie a ze stanu q do p, .Σ lub symbolem ze zbioru εnatomiast a jest słowem pustym
Dla przykładu - ruchami z rysunku 16, który akceptuje ciągεrozpatrzmy diagram przejść AS z symboli zawierających dowolna liczbę zer, po których następuje dowolna liczba jedynek, a następnie dowolna liczba dwójek. Oczywiście zgodnie z definicją dowolna liczba poszczególnych symboli może wynosić 0 czyli nastąpi przejście :εprzy pustym wejściu
0 1 2
ε ε
start q0 q1 q2
Rys.16. NAS -ruchami akceptujący ciąg złożony z kilu 0, potem kilku1, a potem kilku2εz
Dla powyższego diagramu słowo 002 zostanie zaakceptowane gdyż istnieje , q2, o łukachε, εdroga od stanu początkowego do stanu końcowego: q0, q0, q0, , 2.ε, εetykietowanych 0 ,0,
- ruchami jest bardziejεKonstrukcja NAS zrozumiała po zapoznaniu się z wyrażeniami regularnymi, które zostały omówione w następnym rozdziale.
Wyrażenia regularne
Języki akceptowane przez automaty skończone można łatwo opisać prostymi wyrażeniami zwanymi wyrażeniami regularnymi. Celem przedstawienia zapisu języków akceptowanych wprowadźmy pojęcia: złożenia i domknięcia na zbiorach łańcuchów.
będzieΣNiech *.Σ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, nazywamy {xy | x należy do L1 i y należy do 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, 0. Domknięciem Kleene'ego≥} i Li =Lli-1 dla i ε101,1101}. Niech L0={ (domknięciem) L, oznaczanym symbolem L*, nazywamy zbiór:
∞
L* = Li,
i = 0
a domknięciem dodatnim L, oznaczanym symbolem L+, zbiór
∞
L+ = Li,
i = 1
Tak więc L* jest zbiorem wszystkich słów otrzymanych w wyniku złożenia dowolnej liczby słów z L, zaś L+ wyklucza ; np. domknięciemεprzypadek zera słów, których złożenie określa się - , 1, 0, 11,10,01,00....} , zaś domknięciem dodatnim {1,0}+εKleene'ego {1,0}* ={ = {1, 0, 11,10,01,00....}.
Wyrażenia regularne i zbiory przez nie reprezentowane definiujemy w następujący sposób:
• 0 jest wyrażeniem regularnym reprezentującym zbiór pusty.
jest wyrażeniem regularnymε• }.εreprezentującym zbiór {
, a jest wyrażeniem regularnymΣ• Dla każdego a z reprezentują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 S, RS i R*.∪regularnymi reprezentującymi odpowiednio zbiory R
Dla przykładu:
• 00 jest wyrażeniem regularnym, reprezentującym {00}
• (0+1) opisuje zbiór wszystkich łańcuchów złożonych z zer i jedynek
• (0+1)*00(0+1)* opisuje zbiór wszystkich zer i jedynek w których przynajmniej raz wystąpiło podwojenie zer
• (1+10)* reprezentuje zbiór wszystkich zer i jedynek rozpoczynających się od 1 i nie zawierajęcych podwojonych symboli 0.
• (0+1)*011 opisuje wszystkie łańcuchy zer i jedynek kończące się sekwencją 011
• 0+ 1+ 2+ jest wyrażeniem reprezentującym dowolna liczbę zer po których następuje dowolna 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).
Udowodniono, że wyrażenia regularne reprezentują języki akceptowane przez automaty skończone co oznacza, że dla -ruchami, coεdowolnego wyrażenia regularnego istnieje odpowiadający mu NAS z więcej wprowadzono gotowe konstruktory dla diagramów przejść pozwalające dla dowolnego wyrażenia regularnego stworzyć mechanicznie konstrukcję automatu skończonego. Wyróżniono trzy podstawowe postacie wyrażeń regularnych:
• suma teoriomnogościowa r = r1 + r2
• złożenie r = r1 r2
• domknięcie r = r1*
konstruktor dla sumy teoriomnogościowej r= r1+r2
q1 M1 f1
ε ε
start qo fo
ε q2 M2 f2 ε
Każda droga na powyższym diagramie automatu M musi rozpoczynać się od przejścia do stanu q1 lub do stanu q2 przy . Jeżeli droga prowadzi do q1, to następnie może dowolnieεpustym wejściu przebiegać w automacie M1, aż do osiągnięcia stanu f1, potem następuje przejście . Podobnie, jeżeli droga rozpoczęła sięεdo stanu fo, przy pustym wyjściu przejściem ze stanu q0 do q2 to następnie może przebiegać dowolną trasą w automacie M2, aż do osiągnięcia stanu f2, a następnie przejście do stanu f0.
konstruktor dla złożenia r = r1r2
ε
start q1 M1 f1 q2 M2 f2
Każda droga z q1 do f2 w automacie M składa się z drogi etykietowanej jakimś łańcuchem x prowadzącej z q1 do f1, po której następuje przejście ze a następnie następuje droga z q2 doεstanu f1 do stanu q2 przy pustym wejściu f2 etykietowana jakimś łańcuchem y.
konstruktor dla domknięcia r = r1*
ε
ε ε
start q0 q1 M1 f1 f0
ε
Dowolna droga prowadząca , albo też z drogi odεz q0 do f2 składa się albo z drogi z q0 do f0 o etykiecie , po których następuje pewna liczba (w szczególnym przypadku 0)εq0 do q1 przy , następnie znów droga z q1 do f1, aż wεdróg z q1 do f1, potem znowu do q1 przy .εkońcu droga z f2 do f0 przy
Powyższe konstruktory są bardzo pomocne przy kreśleniu diagramów przejść NAS dla wyrażeń regularnych. Konstrukcję takiego automatu rozpoczynamy wtedy od rozłożenia wyrażenia regularnego na elementarne składowe dla których tworzymy automaty, te z kolei na podstawie konstruktorów łączymy w logiczną całość. Przeanalizujmy przykład automatu akceptującego wyrażenie regularne postaci: 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:
start q1 1 q2
wyrażenie r1 możemy zapisać jako r1 = r3 + r4 gdzie r3= 0; r4=1*. Automat dla r3 ma prostą konstrukcję, która przedstawia się następująco:
start q3 0 q4
z kolei wyrażenie r4 możemy zapisać jako r4 = r*5 gdzie r5 to 1, a NAS dla r5 to:
start q5 1 q6
Wykorzystują przedstawione konstruktory zaczniemy kreślenie automatu dla wyrażenia r4 = 1* ( konstruktor domknięcia)
ε
ε ε
start q7 q5 1 q6 q8 rys. a
ε
następnie dla r1 =r3r4 (r= 01*) wykorzystujemy konstruktor złożenia dokładając do rys. a następującą konstrukcję:
ε0
start q3 q4 rys. a
Teraz tworzymy konstrukcję dla wyrażenia r= r1 + r2 (r=01*+1) wykorzystując konstruktor sumy teoriomnogościowej.
start q1 1 q2
ε ε
q9 q10
ε ε
ε ε ε ε0
q3 q4 q7 q5 1 q6 q8
ε
Rys.17. NAS -ruchami dla wyrażenia regularnego 01*+1.εz
Zastosowania automatów skończonych
Istnieje cała gama problemów z zakresu projektowania oprogramowania, które dają się uprościć poprzez automatyczną konwersję symboliki wyrażeń regularnych na efektywną implementację komputerową odpowiedniego automatu skończonego. Teorię automatów skończonych wykorzystano do:
Analizatorów leksykalnych
Tokeny (czyli bazowe kategorie syntaktyczne) języka programowania dają się niemal bez wyjątku przedstawić w postaci wyrażeń regularnych. I tak na przykład, identyfikatory ALGOLu, będące ciągami liter i cyfr rozpoczynającymi się od litery (małej czy dużej), bez ograniczenia co do długości ciągu, można wyrazić w postaci
( litera ) ( litera + cyfra )*
gdzie litera oznacza A + B +... + Z + a + b + .. z, a cyfra - 0 + 1 + .. + 9
Identyfikatory w Fortlanie, których długość jest ograniczona do sześciu znaków i które nie mogą zawierać innych liter niż duże oraz znak $ mogą być przedstawione jako
+ litera + cyfra )5ε( litera ) (
Niektóre generatory analizatorów leksykalnych przyjmują jako wejście ciąg wyrażeń regularnych opisujących tokeny i wytwarzają pojedynczy automat skończony, rozpoznający dowolny token. Zazwyczaj przekształcają one wyrażenia regularne na NAS z -przejściami, a następnie konstruują podzbiory zbioru stanów, aby otrzymać DASε -przejścia.εw sposób bezpośredni, zamiast wyeliminować najpierw
Edytorów tekstu
Pewne edytory tekstu oraz podobne do nich programy pozwalają na zastępowanie dowolnego łańcucha pasującego do danego