Może na początek parę definicji:
$\Sigma$ - alfabet, skończony zbiór symboli
$\Sigma *$zbiór skończonych słów nad zdefiniowanym wyżej alfabete
$L \subseteq \Sigma$ język ( skończony zbiór słów nad alfabetem)
Ponadto załóżmy, że
$0 \in N$
Zadaniem komputerów ma być zwracanie wartości logicznej, czy dane słowo należy do zdefiniowanego alfabetu, czy nie.
Sposoby przedstawiania języków
GRAMATYKI
Zajmiemy się gramatyką generacyjną, to jest taką, która przy pomocy 4 elementów będzie generowała słowa nad alfabetem. Te elementy to:
$\Sigma$ - alfabet terminalny - zbiór wszystkich symboli, które mogą wystąpić w słowach należących do tworzonego przez nas języka
$L$ - alfabet pomocniczy - należą do niego pomocnicze symbole używane w czasie generowania słowa, nie mogą wystąpić w słowach należących do języka
$S$ - symbol startowy; jest to symbol należący do zbioru N, od którego zaczyna się generowanie każdego słowa należącego do języka;
$\rightarrow$ - funkcja przejść, zdefiniowane przez nas reguły, które muszą być stosowane podczas tworzenia języka
Przykładowe gramatyki generacyjne:
1.) Weźmy:
$\Sigma = \left\{ a \right\}$
$N = \left\{ S \right\}$
A także następujące przyporządkowania:
$S \rightarrow a$
$S \rightarrow aS$
Słowa w naszym języku są generowane następująco:
$S \rightarrow aS \rightarrow aaS \rightarrow aaaS \rightarrow ... \rightarrow a^n$ , gdzie $n \in N+$
W dowolnym momencie możemy zastosować przyporządkowanie $S \rightarrow a$ , tworząc słowo.
2.) Weźmy:
$\Sigma = \left\{ a,b \right\}$
$N = \left\{ S \right\}$
I przyporządkowania:
$S \rightarrow aS$
$S \rightarrow b$
Widzimy, że przebieg generowania słowa za pomocą zdefiniowanej przez nas gramatyki wygląda następująco:
$S \rightarrow aS \rightarrow aaS \rightarrow aaaS \rightarrow ... \rightarrow a^nS \rightarrow a^nb$ , gdzie $n \in N+$
Możemy „dokładać” kolejne literki „a” na początku nowego słowa, kończąc jego tworzenie literką b, albo od razu stworzyć jednoliterowe słowo „b”.
3.)Weźmy:
$\Sigma = \left\{ j,a,s,n,e \right\}$
$N= \left\{A,B,C,D,E,S \right\}$
$S \rightarrow aS$
$A \rightarrow j$
$B \rightarrow a$
$C \rightarrow s$
$C \rightarrow aC$
$D \rightarrow n$
$E \rightarrow e$
Przebieg generowania słowa za pomocą zdefiniowanej przez nas gramatyki wygląda następująco:
$S \rightarrow ABCDE \rightarrow jaaCsne \rightarrow jaaaCsne \rightarrow ... \rightarrow ja^msne$ , gdzie $m \in N+$
4.)Przykład trudniejszej gramatyki:
$\Sigma = \left\{ a,b,c \right\}$
$N = \left\{ B,S \right\}$
$S \rightarrow aSBc$
$S \rightarrow aB$
$AB \rightarrow ab$
$bB \rightarrow bb$
$cB \rightarrow Bc$
$S \rightarrow aSBc ABCDE \rightarrow aaSBcBc \rightarrow aaaSBcBcBc \rightarrow a^n(Bc)^n \rightarrow a^naBC(BC)^n \rightarrow abca^n(Bc)^n \rightarrow a^{n+1}b(cB)cBcBc..Bc \rightarrow a^{n+1}bbcBcBc...Bcc \rightarrow a^{n+1}bbBcBc...Bccc \rightarrow a^{n+1}bbbcBcB...cBbbb \rightarrow a^{n+1}b^{n+1}c^{n+1}$ , gdzie $n \in N+$
A teraz zadanie odwrotne: stwórz gramatykę, która generuje słowa postaci:
$a^nb^n$ , $n \in N$
Rozwiązanie:
$\Sigma = \left\{ a,b,c \right\}$
$N= \left\{ S \right\}$
$S \rightarrow aSb$
$S \rightarrow ab$
6.) Stwórz gramatykę, która generuje działania : dodawanie i odejmowanie.
Rozwiązanie:
$\Sigma = \left\{ a,b \right\}$
$N= \left\{ S,A \right\}$
$S \rightarrow a$
$S \rightarrow b$
$S \rightarrow aAb$
$S \rightarrow bAa$
$A \rightarrow +$
$A \rightarrow -$
7.)Stwórz gramatykę, która generuje działania : dodawanie i mnożenie, uwzględniające nawiasy pomiędzy liczbami. Uwaga: dopuszczalne jest nawiasowanie pojedynczej liczby, np. (5).
Rozwiązanie:
$\Sigma = \left\{ a,b \right\}$
$N= \left\{ S,A \right\}$
$S \rightarrow a$
$S \rightarrow b$
$S \rightarrow aAb$
$S \rightarrow bAa$
$S \rightarrow +$
$A \rightarrow *$
$A \rightarrow (S)$
$S \rightarrow S+S$
$S \rightarrow S*S$
Na podstawie definicji funkcji przejść, gramatyki możemy podzielić na 3 klasy, z wyszczególnieniem, iż klasa L3 zawiera się w klasie L2, klasa L2 w L1:
-Gramatyki regularne (L3)
Są to gramatyki, w których funkcje przejść są zdefiniowane następująco:
$A \rightarrow aB$
$A \rightarrow b$
Przykład gramatyki regularnej:
$\Sigma = \left\{ j,a,s,n,e \right\}$
$N= \left\{A,C,D,E,F,S \right\}$
$S \rightarrow A$
$A \rightarrow jC$
$C \rightarrow aC$
$C \rightarrow aD$
$D \rightarrow sE$
$E \rightarrow nF$
$F \rightarrow e$
Każdy łatwo może się domyślić, jakie słowa generuje ta gramatyka ^^.
Języki regularne bardzo łatwo można rozpoznać dzięki (poznanym już przez nas) automatom skończonym
-Gramatyki bezkontekstowe(L2)
Są to gramatyki, w których funkcje przejść są zdefiniowane następująco:
$S \rightarrow \beta$
Przykład gramatyki bezkontekstowej, generującej poprawne adresy e-mail (poprawny adres e-mail definiujemy jako adres następującej postaci: słowo1@słowo2.słowo3. … .słowo n
$\Sigma = \left\{ w,@ , '.' \right\}$
$N= \left\{ A,B,C,S \right\}$
$S \rightarrow �4881�$
$A \rightarrow w$
$B \rightarrow w$
$C \rightarrow w.C$
$C \rightarrow w$
-Gramatyki kontekstowe(L1)
Są to gramatyki, w których funkcje przejść są zdefiniowane następująco:
$\Alpha A \beta \rightarrow \alpha \sigma \beta$
gdzie $\alpha , \beta , \sigma \in \Sigma, \N$
Przekładając to na bardziej ludziki język, słowo musi występować w odpowiednim sąsiedztwie, aby móc użyć funkcji przejścia.
Zadanie domowe:
Napisz gramatykę, która generuje:
1.)ze słowa w słowo o odwróconej kolejności liter (np. z fdsjakfa – afkajsdf)
Rozwiązanie:
$\Sigma = \left\{ a,b \right\}$
$S \rightarrow aSa$
$S \rightarrow bSb$
$S \rightarrow aa$
$S \rightarrow bb$
2.) wszystkie słowa postaci ww, gdzie w – słowo (np. kdjfsskdjfss)
Rozwiązanie:
$\Sigma = \left\{ a,b \right\}$
$N = \left\{ A,B,X \right\}$
$S \rightarrow aAS$
$S \rightarrow bBS$
$S \rightarrow X$
$S \rightarrow aA$
$AX \rightarrow Xa$
$BX \rightarrow Xb$
$X \rightarrow \epsilon$ gdzie $\epsilon$ - słowo puste
Dalsze wywody na temat gramatyk:
I.Czy da się stworzyć gramatykę regularną generującą słowa postaci a^nb^n?
Odpowiedź – nie.
Za każdym razem musielibyśmy pamiętać, ile liter a jest już w słowie, a tego nie da się zrobić. Gramatyki regularne nie potrafią liczyć.
AUTOMATY SKOŃCZONE
Dla niektórych języków za pomocą automatów skończonych możemy sprawdzać, czy dane słowo należy do języka, czy też nie. Dużą ich zaletą jest niewielka ilość pamięci, której potrzebują.
Automaty te składają się ze stanów (niektóre z nich są akceptujące – jeżeli automat skończy w nim przeszukiwać – słowo jest dobre) oraz funkcji przejść.
Przykład automatu skończonego. q0, q1, q2 to stany, strzałkami zobrazowane są funkcje przejść. Słowo dobre dla tego automatu to na przykład aab.
Możemy wyróżnić automaty niedeterministyczne – są to takie automaty, w których ze stanów prowadzą co najmniej dwie funkcje przejść ( automat może „wybrać” , do którego stanu pójdzie).
Ważna rzecz – automat akceptuje słowo, jeżeli MA SZANSĘ je zaakceptować (to znaczy, że sprawdzi wszystkie możliwe kombinacje).
Przykład automatu skończonego niedeterministycznego:
Powiedzmy, że stanem akceptującym (tzn. takim, w którym skończymy przeglądać dane słowo) jest stan q1. Okazuje się wtedy, że dla tego automatu słowami dobrymi są dowolne słowa składające się z liter a, b niezaczynające się na b.
Każdy automat niedeterministyczny możemy zamienić na deterministyczny – po prostu dodając większą liczbę stanów.
Przykład 1. Stwórz gramatykę, którą opisuje poniższy automat:
Rozwiązanie:
$q0 \rightarrow aq0$
$q0 \rightarrow aq1$
$q0 \rightarrow bq2$
$q0 \rightarrow a$
$q1 \rightarrow aq1$
$q1 \rightarrow bq1$
$q1 \rightarrow aa$
$q1 \rightarrow ba$
$q2 \rightarrow aq2$
$q2 \rightarrow bq2$
Przykład 2: Stwórz automt skończony, który akceptuje słowa z poniższej gramatyki:
$S \rightarrow aT$
$T \rightarrow bS$
$S \rightarrow a$
Rozwiązanie:
Wnioski – język gramatyk regularnych =język automatów skończonych
JAK STWIERDZIĆ, CZY DANY JĘZYK JEST REGULARNY?
Aby odpowiedzieć na to pytanie, musimy wprowadzić kilka definicji:
Dwa słowa $U,W \in \Sigma *$ są istotnie różne, jeżeli istnieje takie słowo $Z$, że
słowo $UZ$ należy do zbioru słów języka L, a $WZ$ nie należą do zbioru słów języka L, albo
słowo $WZ$ należy do zbioru słów języka L, a $UZ$ nie należą do zbioru słów języka L
Przykład: słowa $aaa$ i $aaaaa$ są istotnie różne w języki $a^nb^n$, ponieważ istnieje takie słowo, przykładowo $bbb$, że $aaabbb$ należy do $a^nb^n$, a $aaaaabbb$ nie należy do $a^nb^n$ .
Język nie jest regularny, jeżeli istnieje w nim nieskończenie wiele słów istotnie od siebie różnych.
Dowód przez sprzeczność:
Załóżmy, że język $L$ jest językiem regularnym, w którym występuje nieskończenie wiele słów istotnie od siebie różnych. Skoro język ten jest regularny, to da się stworzyć opierający się na nim automat skończony ( o skończonej liczbie stanów). Powiedzmy że czytamy dwa istotnie różne słowa $U$ i $W$. Oczywiście istnieje – bez straty ogólności takie słowo $Z$, że
słowo $UZ$ należy do zbioru słów języka L, a $WZ$ nie należy do zbioru słów języka L.
Powiedzmy, że automat czyta właśnie słowa $U$i $W$. Rozważmy 2 przypadki:
1.Po przeczytaniu tych słów automat jest w tym samym stanie. Po przeczytaniu słowa $Z$ automat przejdzie do pewnego stanu co oznacza, że obydwa słowa $WZ, UZ$ są z języku $L$ - sprzeczność z definicją słów istotnie różnych.
2.Po przeczytaniu tych słów automat jest w różnych stanach – po przeczytaniu słowa $Z$ dla słów $U, W$ automat musi wylądować w dwóch różnych stanach, aby słowa te były istotnie różne. Jednakże mamy nieskończenie wiele różnych par słów istotnie różnych, więc automat musi mieć nieskończenie wiele stanów – sprzeczność, założyliśmy, że jest to automat skończony.
Twierdzenie zostało udowodnione.
Gdyby ktoś znalazł jakiekolwiek błędy (a myślę, że jest ich niemało), proszę o kontakt ^^
