Na dzisiejszych zajęciach zajmiemy się wyrażeniami regularnymi i gramatykami. Wyrażenia regularne to wzorce, które opisują łańcuchy symboli. Aby operować wyrażeniami regularnymi, potrzebne nam będą operandy i jakieś działanie. Jeżeli chodzi o operandy, to możemy mieć jakiś konkretny znak, możemy mieć
, czyli ciąg pusty (zachowuje się jak jedynka), zbiór pusty
(zachowuje się jak 0), oraz jakąś zmienną. Teraz jakie działania możemy przeprowadzić na tych wyrażeniach regularnych. Będzie to:

Suma:

Złożenie:

Domknięcie Kleene'go:

Domknięcie z plusem:

Najwyższy priorytet posiadają domknięcia. Z kolei najniższy - suma. Taka jest kolej działań. Istnieje kilka reguł dotyczących działań na wyrażeniach regularnych. Oto i one:

Teraz zdefiniujmy kilka wyrażeń regularnych. Na początek definicja dowolnego ciągu zerojedynkowego:
. Jak widać został w tym ciągu użyty ciąg zer, ciąg jedynek, kombinacje zera z jedynką, oraz pustość, która sugeruje, że ciąg może być także. A teraz jak zdefiniować ciąg zerojedynkowy kończący się dwiema jedynkami (niepusty). Można to zrobić w taki sposób:
. Zdefiniujmy teraz ciąg zerojedynkowy niepusty, który zawiera jedynkę umieszczoną w samym środku ciągu:

(0|1)*1(0|1)*. A teraz kolejne zadanie. Jak zdefiniować ciąg, który zawiera maksymalnie jedną jedynkę i nie jest ona początkiem ani końcem ciągu. Oto sposób w jaki można to zapisać:
. A teraz jak zdefiniować ciąg zerojedynkowy, który na trzeciej pozycji od prawej strony posiada jedynkę. Można zrobić to tak: (0|1)*1(0|1)(0|1). Nim dalej będziemy definiować kolejne wyrażenia warto wspomnieć, że suma może zostać przyrównana do alternatywy, złożenie do mnożenia, a domknięcie do powtórzenia elementu. Teraz pytanie. Jak zdefiniować ciąg zerojedynkowy, w którym wszystkie zera są poprzednikami jedynek (po zerze w ciągu musi się pojawić od razu jedynka). Można to zrobić tak:
. A teraz pytanie. Jak za pomocą wyrażeń regularnych można zapisać identyfikator w języku c (nazwy, które można nadawać zmiennym, funkcjom i procedurom). Można to zrobic tak. Mamy dane zbiory:

litera = A|B|…|Z|a|b|…|z|_

cyfra = 0|1|…|9

Zapis będzie miał wówczas postać taką: litera(litera|cyfra)*. Przejdźmy teraz do konwersji wyrażeń regularnych na automaty skończone. Popatrzmy najpierw jak by wyglądał taki automat skończony:

Powyższy automat przedstawia wyrażenie regularne postaci a|bc*. Automat ma koniec w wierzchołku numer 4 i ma dwie drogi. Jedna droga idzie od jedynki do czwórki. Automat wówczas zwraca wartość
. Z kolei druga droga idzie od 1, 5 do 10 i potem do 4. Po takim przejściu są zwracane wartości:
. A teraz narysujmy taki automat, który będzie przedstawiał nastepujące wyrażenie: (ab)*|(cd)+. Wykonamy nastepujący rysunek automatu z przejściami:

I teraz kolejne zadanie. Należy narysować automat skończony, który będzie ilustracją wyrażenia: ((aa)|b). Na wyjściu ma być więc podany wynik aa albo b.

I ostatnie zadaie z wyrażeń. Jak za pomocą wyrażenia regularnego zapisać operaory porównywania w c. Mamy 6 operatorów porównywania w c:

== - równy

!= - nierówny

<= - mniejszy równy

>= = większy równy

> - większy

< - mniejszy

Oto sposób zapisu: (=|!|<|>)=|>|<. Gramatyka różni się od wyrażenia regularnego sposobem zapisywania wzorców. Przyjmijmy za wyr jakieś wyrażenie. Przyjmijmy, że <> to jakiś metrosymbol, a +, -, *, /, (, ) to symbole terminalne. Wyrażenie może być liczbą co zapisujemy jako: <wyr> -> <liczba>. Wyrażenie może być też wyrażeniem złozonym (w nawiasie), czyli: wyr -> (<wyr>). A także wyrażenie może być sumą, różnicą, ilorazem i iloczynem dwóch wyrażeń:

<wyr> -> <wyr> + <wyr>

<wyr> -> <wyr> - <wyr>

<wyr> -> <wyr> * <wyr>

<wyr> -> <wyr> / <wyr>

Oznaczmy za cyfra jakąś cyfrę z przedziału od 0 do 9 co można zapisać jako: <cyfra> -> 0|1|2|3|…|9. Każda liczba może być cyfrą, co można zapisać jako: <liczba> -> <cyfra>. Ponadto liczba może być wielocyfrowa, co można przedstawić jako:

<liczba> -> <liczba><cyfra>. Popatrzmy dla przykładu jak sprawdzić, czy jakieś wyrażenie zostało zapisane zgodnie z tą gramatyką. Załóżmy, że mamy wyrażenie (5*(128-70). Za w oznaczmy wyrażenie za l liczbę, a za c cyfrę. Przedstawiamy je za pomoca następującego drzewa gramatycznego:

I teraz kilka kolejnych reguł. Litera może być przedstawiona jako: <litera> -> A|B|…|Z|a|b|…|z|_ Z kolei cyfra jako: <cyfra> -> 0|1|2|3|…|9. Ponadto niech dla jakiegoś identyfikatora trzycyfrowego złożonego z dwóch liter i jednej cyfry będą określone nastepujące reguły:

<identyfikator> -> <litera>

<identyfikator> -> <identyfikator><litera>

<identyfikator> -> <identyfikator><cyfra>

Załóżmy, że mamy identyfikator ab8. Jak go przedstawić za pomocą gramatycznego drzewa. Oto, jak to się robi. Nich i będzie identyfikatorem, c cyfrą, a l literą:

Spróbujmy teraz za pomocą gramatyki zdefiniować typową instrukcję dla języka c. Instrukcję oznaczmy jako instr, instrukcję prostą jako ip, warunek jako war, listę instrukcji jako lista. I mamy:

<instr> -> ip

<instr> -> while (war) <instr>

<lista> ->

<lista> -> <instr><lista>

<instr> -> {<lista>}

<instr> -> if (war) <instr>

<instr> -> if (war) <instr> else <instr>

I teraz będziemy pokazywać jakie według tej powyższej gramatyki słowa mogą należeć do języków kategorii symantycznych (jaką postać będzie miała instrukcja i lista przy kolejnych przebiegach). Rozrysujmy taką tabelę (pierwsza kolumna przedstawia numer przebiegu, druga - język od instrukcji i trzecia - język od zdefiniowanej listy):

Przebieg	L(<instr>)	L(<lista>)
0
1	ip;
2	while (war) ip;
3	while (war) while(war) ip;	ip,ip; while(war) ip;
4	while (war) {}	while (war) ip, ip;
5	{ip;}	{} {} ip;

Przebieg 0 oznacza pustą zawartość instrukcji, jak i listy. Przy pierwszym przebiegu dodana została do instrukcji jakaś instrukcja prosta. Dlatego, że instrukcja została już zdefiniowana, mamy epsilon po stronie listy. Kolejne przebiegi rozszerzają definicję instrukcji. Warto wiedzieć, że każde wyrażenie regularne da się przekonwertować na gramatykę, natomiast nie każda gramatyka da się przekonwertować na wyrażenie regularne. Rozpatrzmy przykład, którym będzie ciąg mający tyle samo zer co jedynek, czyli mniej więcej taki:

01

0011

000111 …

Powyższego przykładu nie da się zapisać w postaci wyrażenia regularnego, ale da się powyższy przykład zapisać w formie gramatyki:

<S> -> 01

<S> -> 0 <S> 1

A teraz popatrzmy jak by przebiegało tworzenie gramatyki na podstawie wyrażenia regularnego. Oznaczmy za L(R) to język od jakiegoś wyrażenia regularnego R. I spójrzmy na konstrukcję (Po lewej stronie mamy wyrażenie regularne, a po prawej gramatykę):

L(R) = L(<S>)

L(R) = {x} <S> -> x

L(R) = {
} <S> ->

L(R) =

Rozpatrzmy teraz taki przykład wyrażenia regularnego, że R = R1 | R2. Aby zamienić to na gramatykę należy wprowadzić założenie, że L(R1) = L(S1) i L(R2) = L(S2). Wówczas mamy:

gramatykę:

<S> -> <S1>

<S> -> <S2> stąd: <S>-><S1>|<S2>

Z kolei jeśli byśmy mieli wyrażenie regularne będące złożeniem R = R1 R2, to gramatyka miałaby postać <S> -> <S1><S2>. A co gdyby R = R1*. Wtedy:

<S> ->

<S> -> <S1><S> stąd: <S> -> <S1><S>|

A co gdybyśmy mieli R = R1+. Wówczas:

<S> -> <S1>

<S> -> <S1><S> stąd: <S> -> <S1><S> -> <S1>

A teraz rozpatrzmy dwa konkretniejsze przykłady. Pierwszy z nich to R = a|bc*. Oto rozpisana gramatyka dla tego wyrażenia:

<A> -> a

<B> -> b

<C> -> c

<D> -> <C><D>|

<E> -> <B><D>

<F> -> <A>|<E>

L(R) = L(<F>)

I ostatni przykład dla (ab)*|(ed)+. I mamy:

<A> -> a

<B> -> b

<C> -> e

<D> -> d

<E> -> <A><B>

<F> -> <C><F>|

<G> -> <E><D>

<H> -> <G><H>|<G>

<J> -> <F>|<H>

---