Język regularny: Różnice pomiędzy wersjami

: <math>A \rightarrowto B</math>

: <math>A \rightarrowto xB</math>

: <math>A \rightarrowto x</math>

: <math>A \rightarrowto xyz</math>

: <math>A \rightarrowto xyzB</math>

: <math>A \rightarrowto \epsilon</math>

: <math>A \rightarrowto BC</math> (dopuszczalne w [[gramatyka bezkontekstowa|gramatykach bezkontekstowych]])

: <math>AB \rightarrowto CDB</math> (dopuszczalne w [[gramatyka kontekstowa|gramatykach kontekstowych]])

* Każdy język regularny '''można''' zapisać za pomocą gramatyki regularnej.

* Każda gramatyka regularna '''generuje''' pewien język regularny.

* Język, który '''nie jest''' regularny '''nie posiada''' gramatyki regularnej.

Zbiór wszystkich języków regularnych oznacza się przez ''<math>REG.</math>''.

* [[Domknięcie Kleene’ego|domknięcia Kleene'egoKleene’ego]]

** np. język składający się tylko z 0 i 1 po zastosowaniu domknięcia Kleene'egoKleene’ego jest językiem wszystkich słów zerojedynkowych.

Do testowania, czy dane słowo należy do danego języka regularnego można zawsze zbudować '''deterministyczny automat skończony''' – maszynę która ma skończoną liczbę stanów, oraz funkcję przejścia, zmieniającą jej stan po przeczytaniu każdego kolejnego znaku w zależności od przeczytanego znaku oraz stanu aktualnego. Niektóre z tych stanów oznaczone są jako [[stan akceptujący|akceptujące]] – tzn. że przeczytany dotychczas fragment jest poprawnym słowem języka, dla którego zbudowano automat.

Rodzinę języków rozpoznawalnych przez automaty skończone oznacza się przez ''<math>REC.</math>''.

* Stany automatu to Start, ZaczynaSięOdJedynki i ZaczynaSięOdZera.

* Automat zaczyna w stanie Start.

* Jeśli automat jest w stanie Start, to po przeczytaniu 0 przechodzi w stan ZaczynaSięOdZera.

* Jeśli automat jest w stanie Start, to po przeczytaniu 1 przechodzi w stan ZaczynaSięOdJedynki.

* Automat akceptuje słowo, jeśli po przeczytaniu całego znajduje się w stanie ZaczynaSięOdJedynki.

* Stany automatu to Start, OstatniZnakToJedynka i OstatniZnakToZero.

* Automat zaczyna w stanie Start.

* Po przeczytaniu 0, niezależnie od poprzedniego stanu, automat przechodzi w stan OstatniZnakToZero.

* Po przeczytaniu 1, niezależnie od poprzedniego stanu, automat przechodzi w stan OstatniZnakToJedynka.

* Automat akceptuje słowo, jeśli po przeczytaniu całego znajduje się w stanie OstatniZnakToJedynka.

Automat służący do sprawdzania czy dane słowo binarne ma <math>n</math> lub <math>m</math> (<math>(n > m)</math>) znaków mógłby wyglądać tak:

* Stany to <math>S_0,</math>, <math>S_1,</math>, <math>S_2,</math>, aż do <math>S_n,</math>, i stan ZaDługie.

* Stan początkowy to <math>S_0.</math>

* Jeśli automat jest w stanie <math>S_k</math> (<math>(k \not=neq n),</math>), to po przeczytaniu dowolnego znaku przechodzi w stan <math>S_{k+1}.</math>

* Jeśli automat jest w stanie <math>S_n,</math>, to po przeczytaniu dowolnego znaku przechodzi w stan ZaDługie.

* Akceptujące są stany <math>S_n</math> i <math>S_m.</math>

Twierdzenie Kleene’ego dokładnie określa relacje pomiędzy rodzinami języków ''<math>REC</math>'' (rozpoznawalnych) i ''<math>REG</math>'' (regularnych). Mianowicie, dla dowolnego alfabetu (skończonego) zachodzi ''<math>REC = REG.</math>''. Dowód tego twierdzenia przeprowadza się na zasadzie obustronnej inkluzji (ale jest on długi i zostaje pominięty).

* <math>S \rightarrowto^0 S</math>

* <math>S \rightarrowto^1 S</math>

* <math>S \rightarrowto^1 X_1</math> – jedynym niedeterministycznym przejściem jest przejście ze stanu <math>S</math> po przeczytaniu jedynki, albo w <math>S,</math>, albo w <math>X_1</math>

* <math>X_1 \rightarrowto^0 X_2</math>

* <math>X_1 \rightarrowto^1 X_2</math>

* <math>X_2 \rightarrowto^0 X_3</math>

* <math>X_2 \rightarrowto^1 X_3</math>

* <math>X_3 \rightarrowto^0 X_4</math>

* <math>X_3 \rightarrowto^1 X_4</math>

* <math>X_4 \rightarrowto^0 S</math>

* <math>X_4 \rightarrowto^1 S</math>

* Stan startowy to <math>S,</math>, stanem akceptującym jest <math>X_4.</math>

Możemy uruchomić ten automat na słowie <math>0101000{:}</math>:

: <math>S \rightarrowto^0 S \rightarrowto^1 S \rightarrowto^0 S \rightarrowto^1 X_1 \rightarrowto^0 X_2 \rightarrowto^0 X_3 \rightarrowto^0 X_4.</math>

: <math>S \rightarrowto^0 S \rightarrowto^1 X_1 \rightarrowto^0 X_2 \rightarrowto^1 X_3 \rightarrowto^0 X_4 \rightarrowto^0 S \rightarrowto^0 S,</math>

: <math>S \rightarrowto^0 S \rightarrowto^1 S \rightarrowto^0 S \rightarrowto^1 S \rightarrowto^0 S \rightarrowto^0 S \rightarrowto^0 S.</math>

Na początku bierzemy więc zbiór złożony jedynie ze stanu startowego emulowanego NFA, po każdym kroku zaś zbiór takich stanów <math>X,</math>, że w poprzednim zbiorze był jakiś stan <math>Y,</math>, i możliwe jest dla aktualnie czytanego znaku przejście z <math>Y</math> w <math>X.</math>. Czyli w interpretacji ścieżkowej – takich stanów <math>X,</math>, że na którejś ze ścieżek krok wcześniej był stan <math>Y,</math>, i że jest możliwe przedłużenie tej ścieżki w tym kroku do <math>X.</math>.

Przyjmując zbiory stanów NFA za stany DFA, każde NFA możemy emulować w pełni deterministycznie na DFA. Być może jednak liczba stanów będzie musiała wzrosnąć wykładniczo.

Weźmy podany wyżej automat rozpoznający słowa, których czwartym od końca znakiem jest jedynka. Następuje wykładnicza eksplozja liczby stanów:

: <math>\{S\} \rightarrowto^01 \{S,X_1\}</math>

: <math>\{S,X_1\} \rightarrowto^10 \{S,X_1X_2\}</math>

: <math>\{S,X_1\} \rightarrowto^01 \{S,X_1,X_2\}</math>

: <math>\{S,X_1X_2\} \rightarrowto^10 \{S,X_1,X_2X_3\}</math>

: <math>\{S,X_2\} \rightarrowto^01 \{S,X_1,X_3\}</math>

: <math>\{S,X_1,X_2\} \rightarrowto^10 \{S,X_1X_2,X_3\}</math>

: <math>\{S,X_1,X_2\} \rightarrowto^01 \{S,X_1,X_2,X_3\}</math>

: <math>\{S,X_1,X_2X_3\} \rightarrowto^10 \{S,X_1,X_2,X_3X_4\}</math>

: <math>\{S,X_3\} \rightarrowto^01 \{S,X_1,X_4\}</math>

: <math>\{S,X_1,X_3\} \rightarrowto^10 \{S,X_1X_2,X_4\}</math>

: <math>\{S,X_1,X_3\} \rightarrowto^01 \{S,X_1,X_2,X_4\}</math>

: <math>\{S,X_1X_2,X_3\} \rightarrowto^10 \{S,X_1,X_2X_3,X_4\}</math>

: <math>\{S,X_2,X_3\} \rightarrowto^01 \{S,X_1,X_3,X_4\}</math>

: <math>\{S,X_1,X_2,X_3\} \rightarrowto^10 \{S,X_1X_2,X_3,X_4\}</math>

: <math>\{S,X_1,X_2,X_3\} \rightarrowto^01 \{S,X_1,X_2,X_3,X_4\}</math>

: <math>\{S,X_1,X_2,X_3X_4\} \rightarrowto^10 \{S,X_1,X_2,X_3,X_4\}</math>

: <math>\{S,X_4\} \rightarrowto^01 \{S,X_1\}</math>

: <math>\{S,X_1,X_4\} \rightarrowto^10 \{S,X_1X_2\}</math>

: <math>\{S,X_1,X_4\} \rightarrowto^01 \{S,X_1,X_2\}</math>

: <math>\{S,X_1X_2,X_4\} \rightarrowto^10 \{S,X_1,X_2X_3\}</math>

: <math>\{S,X_2,X_4\} \rightarrowto^01 \{S,X_1,X_3\}</math>

: <math>\{S,X_1,X_2,X_4\} \rightarrowto^10 \{S,X_1X_2,X_3\}</math>

: <math>\{S,X_1,X_2,X_4\} \rightarrowto^01 \{S,X_1,X_2,X_3\}</math>

: <math>\{S,X_1,X_2X_3,X_4\} \rightarrowto^10 \{S,X_1,X_2,X_3X_4\}</math>

: <math>\{S,X_3,X_4\} \rightarrowto^01 \{S,X_1,X_4\}</math>

: <math>\{S,X_1,X_3,X_4\} \rightarrowto^10 \{S,X_1X_2,X_4\}</math>

: <math>\{S,X_1,X_3,X_4\} \rightarrowto^01 \{S,X_1,X_2,X_4\}</math>

: <math>\{S,X_1X_2,X_3,X_4\} \rightarrowto^10 \{S,X_1,X_2X_3,X_4\}</math>

: <math>\{S,X_2,X_3,X_4\} \rightarrowto^01 \{S,X_1,X_3,X_4\}</math>

: <math>\{S,X_1,X_2,X_3,X_4\} \rightarrowto^10 \{S,X_1X_2,X_3,X_4\}</math>

: <math>\{S,X_1,X_2,X_3,X_4\} \rightarrowto^01 \{S,X_1,X_2,X_3,X_4\}</math>

Przy czym akceptujące są stany zawierające <math>X_4,</math>, stan startowy to zaś <math>\{S\}.</math> Jedynym co choć trochę ogranicza liczbę stanów jest to, że stan <math>S</math> jest zawsze osiągalny, więc nie musimy uwzględniać zbiorów stanów nie zawierających <math>S.</math>

Sprawdźmy tym automatem słowo <math>0101000{:}</math>:

: <math>\{S\} \rightarrowto^0 \{S\} \rightarrowto^1 \{S,X_1\} \rightarrowto^0 \{S,X_2\} \rightarrowto^1 \{S,X_1,X_3\} \rightarrowto^0 \{S,X_2,X_4\} \rightarrowto^0 \{S,X_3\} \rightarrowto^0 \{S,X_4\}.</math>

Jeszcze jedną metodą wyrażania języków regularnych są [[Wyrażenie regularne|wyrażenia regularne]]. Wyrażenie takie <math>X</math> tworzy się używając:

* symboli nieterminali <math>\epsilonx</math> – oznaczającegooznaczających język złożony zez słowapojedynczego pustegonieterminala <math>x,</math>

* symboli nieterminalikonkatenacji <math>xX_1 X_2</math> – oznaczającychoznacza to język złożony zze słów, które można podzielić tak, że pierwsza część należy do <math>X_1,</math> druga pojedynczegozaś nieterminalado <math>xX_2,</math>

* konkatenacjialternatywy <math>X_1 | X_2</math> – oznacza to język złożony zez wszystkich słów, które można podzielić tak, że pierwsza część należy do <math>X_1</math>, drugaoraz zaśwszystkich dosłów <math>X_2,</math>.

* alternatywygwiazdki <math>X_1 | X_2X^*</math> – oznacza to język złożony z wszystkichze słów, <math>X_1</math>które orazmożna wszystkichpodzielić słówna 0 lub więcej fragmentów, z których każdy należy do <math>X_2X.</math>

* plus (jedno lub więcej wystąpień) – <math>X^+ = X X^*,</math>

* znak zapytania (wystąpienie opcjonalne) – <math>X? = X | \epsilon,</math>

* n-krotne wystąpienie – <math>X^{n} = X X^{n-1} = \cdots</math>

== [[Twierdzenie Myhilla-Nerode'aNerode’a]] ==

[[Twierdzenie Myhilla-Nerode'aNerode’a]] podaje dostateczny i konieczny warunek na to, by język był regularny.

* prefiksy o parzystej ilości jedynek i zer – prawidłowe sufiksy mają parzyście wiele jedynek i nieparzyście wiele zer,

* prefiksy o parzystej ilości jedynek i nieparzystej zer – prawidłowe sufiksy mają parzyście wiele jedynek i zer,

* prefiksy o nieparzystej ilości jedynek i parzystej zer – prawidłowe sufiksy mają nieparzyście wiele jedynek i zer,

* prefiksy o nieparzystej ilości jedynek i zer – prawidłowe sufiksy mają parzyście wiele zer i nieparzyście wiele jedynek.

Weźmy język <math>\{a^nb^n : n\in N\},</math>, czyli wszystkich słów składających się z <math>n</math> znaków <math>a,</math>, po których występuje <math>n</math> znaków <math>b,</math>, dla dowolnego <math>n.</math>.

Weźmy ciąg <math>p_k</math> prefiksów postaci <math>a^k,</math>, dla kolejnych <math>k.</math>. <math>b^j</math> należy do zbioru <math>S_k</math> poprawnych sufiksów dla prefiksu <math>p_k</math> wtedy i tylko wtedy, gdy <math>a^kb^j</math> należy do tego języka, a więc gdy <math>k=j.</math> Czyli zbiory poprawnych sufiksów dla każdych dwóch prefiksów z naszego nieskończonego ciągu są różne, co przez twierdzenie o indeksie dowodzi, że język ten nie jest regularny.

Załóżmy, że dany język jest regularny. Wtedy istnieje taka stała <math>n,</math>, że dla każdego słowa <math>w</math> należącego do tego języka i dłuższego niż <math>n,</math> możemy to słowo podzielić na trzy części <math>xyz,</math> z czego <math>n > |xy|</math> i <math>|y| > 0,</math> i dla każdego <math>k</math> całkowitego nieujemnego, <math>xy^kz</math> należy do języka.

Weźmy język <math>L=\{a^mb^m : m\in N\},</math>, czyli wszystkich słów składających się z <math>m</math> znaków <math>a,</math>, po których występuje <math>m</math> znaków <math>b,</math>, dla dowolnego <math>m</math> naturalnego.

Weźmy słowo <math>a^mb^m\in L,</math>, gdzie <math>m</math> jest większe od stałej <math>n</math> z lematu o pompowaniu. Wobec warunku <math>|xy|<n</math> z lematu, <math>y</math> leży w całości w części <math>a^m.</math> Wtedy <math>xy^2z</math> ma więcej znaków <math>a</math> niż <math>b,</math> gdyż <math>|y|>0.</math> Zatem słowo <math>xy^2z</math> nie należy do <math>L,</math> wbrew tezie lematu o pompowaniu.