Język regularny

Z Wikipedii

Język regularny (ang. regular language) to język formalny taki, że istnieje automat o skończonej liczbie stanów potrafiący zdecydować, czy dane słowo należy do języka.

Wszystkie języki regularne są bezkontekstowe.

Spis treści

1 Gramatyka regularna
2 Przykładowe języki regularne
3 Operacje na językach regularnych
4 Deterministyczne automaty skończone (DFA)
5 Niedeterministyczne automaty skończone (NFA)
6 Wyrażenia regularne
7 Twierdzenie Myhilla-Nerode'a
- 7.1 Przykład
- 7.2 Przykład (2)
8 Lemat o pompowaniu
- 8.1 Przykład

[edytuj] Gramatyka regularna

Każdy język regularny można zapisać w postaci gramatyki formalnej – takiej gramatyki, że po lewej stronie każdej reguły jest jeden symbol nieterminalny, po prawej zaś dowolna liczba symboli terminalnych, po których występuje co najwyżej jeden symbol nieterminalny.

Regułami gramatyki regularnej są więc na przykład:

$A \rightarrow B$

$A \rightarrow xB$

$A \rightarrow x$

$A \rightarrow xyz$

$A \rightarrow xyzB$

$A \rightarrow \epsilon$

Nie są zaś nimi na przykład:

$A \rightarrow BC$ (dopuszczalne w gramatykach bezkontekstowych)

$AB \rightarrow CD$ (dopuszczalne w gramatykach kontekstowych)

Zależności między językami regularnymi a gramatykami regularnymi są następujące:

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
Gramatyka, która nie jest regularna może generować język regularny, acz nie musi. Jeśli takowy generuje, ma on też inną gramatykę, która jest regularna.

[edytuj] Przykładowe języki regularne

Regularnymi są np. języki:

zbiór wszystkich słów alfabetu ${0,1}$
zbiór wszystkich słów alfabetu ${0,1}$ o długości $n$
zbiór wszystkich słów alfabetu ${0,1}$ o parzystej długości
zbiór wszystkich słów alfabetu ${0,1}$ zaczynających się od zera
zbiór wszystkich słów alfabetu ${0,1}$ nie zaczynających się od zera
zbiór wszystkich słów alfabetu ${0,1}$ w których na przemian występują zera i jedynki
zbiór wszystkich słów alfabetu ${0,1,2}$ w których na przemian występują zera, jedynki i dwójki

[edytuj] Operacje na językach regularnych

Regularne zawsze są:

Dopełnienie dowolnego języka regularnego
- Skoro język słów długości n jest regularny, jest więc nim też język słów o długości różnej od n.
Alternatywa dowolnych języków regularnych
- Język słów parzystej długości jest regularny, jest nim też język słów zaczynających się od zera. Regularny jest więc język słów które są parzyste lub zaczynają się od zera.
Przecięcie dowolnych języków regularnych
- Język słów parzystej długości jest regularny, jest nim też język słów zaczynających się od zera. Regularny jest więc język słów które są parzyste oraz zaczynają się od zera.
Język słów dowolnego języka regularnego L, tyle że zapisanych od końca.
- Język słów nie zaczynających się od zera jest regularny, Jest nim więc też język słów nie kończących się zerem.
Język słów stanowiących konkatenację słów dowolnych języków regularnych
- Język słów które można podzielić tak, że początkowa część słowa składa się z naprzemiennie ustawionych zer i jedynek, a końcowa z naprzemiennie ustawionych zer, jedynek i dwójek, jest regularny.

[edytuj] Deterministyczne automaty skończone (DFA)

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 akceptujące - tzn. że przeczytany dotychczas fragment jest poprawnym słowem języka, dla którego zbudowano automat.

[edytuj] Przykład automatu deterministycznego

Automat służący do sprawdzania czy dane słowo binarne zaczyna się od jedynki mógłby wyglądać tak:

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
Jeśli automat jest w dowolnym innym stanie, po przeczytaniu jakiegokolwiek znaku nie zmienia stanu.
Automat akceptuje słowo, jeśli po przeczytaniu całego znajduje się w stanie ZaczynaSięOdJedynki

[edytuj] Przykład automatu deterministycznego (2)

Automat służący do sprawdzania czy dane słowo binarne kończy się jedynką mógłby wyglądać tak:

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

[edytuj] Przykład automatu deterministycznego (3)

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

Stany to $S 0$ , $S 1$ , $S 2$ , aż do $S n$ , i stan ZaDługie
Stan początkowy to $S 0$
Jeśli automat jest w stanie $S k$ ( $k \not= n$ ), to po przeczytaniu dowolnego znaku przechodzi w stan $S k + 1$
Jeśli automat jest w stanie $S n$ , to po przeczytaniu dowolnego znaku przechodzi w stan ZaDługie.
Jeśli automat jest w stanie ZaDługie, po przeczytaniu dowolnego znaku pozostaje w stan ZaDługie.
Akceptujące są stany $S n$ i $S m$

[edytuj] Niedeterministyczne automaty skończone (NFA)

Zamiast automatu deterministycznego można też użyć niedeterministycznego – różni się on tym, że ten sam stan aktualny i znak odczytany mogą go przeprowadzić w wiele różnych stanów – funkcja przejścia zmienia się w relację przejścia. Automat taki akceptuje słowo, jeśli jest w stanie dojść do stanu akceptującego. Być może dane słowo generowało też wiele innych ciągów stanów, które nie prowadziły do stanu akceptującego – nie ma to znaczenia w kwestii akceptacji.

Automaty deterministyczne są szczególnym przypadkiem automatów niedeterministycznych – zawsze możliwe jest w nich tylko jedno przejście – każde słowo generuje więc tylko jeden ciąg stanów, i kryteria akceptacji upraszczają się do kryteriów dla DFA.

Wydawać by się mogło, że NFA powinny być silniejsze od DFA. Tak jednak nie jest, i każdy NFA można za pomocą prostej procedury przeprowadzić w DFA.

[edytuj] Przykład

Weźmy NFA rozpoznające język słów nad alfabetem binarnym, których czwartym od końca znakiem jest 1:

$S \rightarrow^0 S$
$S \rightarrow^1 S$
$S \rightarrow^1 X_1$ – jedynym niedeterministycznym przejściem jest przejście ze stanu $S$ po przeczytaniu jedynki, albo w $S$ , albo w $X 1$
$X_1 \rightarrow^0 X_2$
$X_1 \rightarrow^1 X_2$
$X_2 \rightarrow^0 X_3$
$X_2 \rightarrow^1 X_3$
$X_3 \rightarrow^0 X_4$
$X_3 \rightarrow^1 X_4$
$X_4 \rightarrow^0 S$
$X_4 \rightarrow^1 S$
Stan startowy to $S$ , stanem akceptującym jest $X 4$

Możemy uruchomić ten automat na słowie $0101000$ :

$S \rightarrow^0 S \rightarrow^1 S \rightarrow^0 S \rightarrow^1 X_1 \rightarrow^0 X_2 \rightarrow^0 X_3 \rightarrow^0 X_4$

Choć możemy też uruchomić go tak, żeby nie zaakceptował słowa:

$S \rightarrow^0 S \rightarrow^1 X_1 \rightarrow^0 X_2 \rightarrow^1 X_3 \rightarrow^0 X_4 \rightarrow^0 S \rightarrow^0 S$

$S \rightarrow^0 S \rightarrow^1 S \rightarrow^0 S \rightarrow^1 S \rightarrow^0 S \rightarrow^0 S \rightarrow^0 S$

[edytuj] Konwersja NFA do DFA

Pomyślmy jak można emulować NFA na deterministycznym komputerze. Pierwsza myśl to wypróbowanie wszystkich możliwych ciągów stanów i sprawdzenie czy nie ma wśród nich jakiegoś stanu akceptującego. Metoda ta, acz poprawna, generuje jednak potencjalnie wykładniczo wiele ścieżek w porównaniu do długości słowa.

Nie musimy jednak pamiętać wszystkich ścieżek. Nieważne, co znajdowało się na początku ścieżki – nam wystarcza wiedza, jakie stany występują na dowolnej ze ścieżek po $k$ krokach.

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 $X$ , że w poprzednim zbiorze był jakiś stan $Y$ , i możliwe jest dla aktualnie czytanego znaku przejście z $Y$ w $X$ . Czyli w interpretacji ścieżkowej – takich stanów $X$ , że na którejś ze ścieżek krok wcześniej był stan $Y$ , i że jest możliwe przedłużenie tej ścieżki w tym kroku do $X$ .

Słowo jest akceptowane jeśli wśród zbioru stanów po przeczytaniu całego znajduje się choć jeden stan akceptujący.

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.

[edytuj] Przykład konwersji

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:

$\{S\} \rightarrow^0 \{S\}$

$\{S\} \rightarrow^1 \{S,X_1\}$

$\{S,X_1\} \rightarrow^0 \{S,X_2\}$

$\{S,X_1\} \rightarrow^1 \{S,X_1,X_2\}$

$\{S,X_2\} \rightarrow^0 \{S,X_3\}$

$\{S,X_2\} \rightarrow^1 \{S,X_1,X_3\}$

$\{S,X_1,X_2\} \rightarrow^0 \{S,X_2,X_3\}$

$\{S,X_1,X_2\} \rightarrow^1 \{S,X_1,X_2,X_3\}$

$\{S,X_3\} \rightarrow^0 \{S,X_4\}$

$\{S,X_3\} \rightarrow^1 \{S,X_1,X_4\}$

$\{S,X_1,X_3\} \rightarrow^0 \{S,X_2,X_4\}$

$\{S,X_1,X_3\} \rightarrow^1 \{S,X_1,X_2,X_4\}$

$\{S,X_2,X_3\} \rightarrow^0 \{S,X_3,X_4\}$

$\{S,X_2,X_3\} \rightarrow^1 \{S,X_1,X_3,X_4\}$

$\{S,X_1,X_2,X_3\} \rightarrow^0 \{S,X_2,X_3,X_4\}$

$\{S,X_1,X_2,X_3\} \rightarrow^1 \{S,X_1,X_2,X_3,X_4\}$

$\{S,X_4\} \rightarrow^0 \{S\}$

$\{S,X_4\} \rightarrow^1 \{S,X_1\}$

$\{S,X_1,X_4\} \rightarrow^0 \{S,X_2\}$

$\{S,X_1,X_4\} \rightarrow^1 \{S,X_1,X_2\}$

$\{S,X_2,X_4\} \rightarrow^0 \{S,X_3\}$

$\{S,X_2,X_4\} \rightarrow^1 \{S,X_1,X_3\}$

$\{S,X_1,X_2,X_4\} \rightarrow^0 \{S,X_2,X_3\}$

$\{S,X_1,X_2,X_4\} \rightarrow^1 \{S,X_1,X_2,X_3\}$

$\{S,X_3,X_4\} \rightarrow^0 \{S,X_4\}$

$\{S,X_3,X_4\} \rightarrow^1 \{S,X_1,X_4\}$

$\{S,X_1,X_3,X_4\} \rightarrow^0 \{S,X_2,X_4\}$

$\{S,X_1,X_3,X_4\} \rightarrow^1 \{S,X_1,X_2,X_4\}$

$\{S,X_2,X_3,X_4\} \rightarrow^0 \{S,X_3,X_4\}$

$\{S,X_2,X_3,X_4\} \rightarrow^1 \{S,X_1,X_3,X_4\}$

$\{S,X_1,X_2,X_3,X_4\} \rightarrow^0 \{S,X_2,X_3,X_4\}$

$\{S,X_1,X_2,X_3,X_4\} \rightarrow^1 \{S,X_1,X_2,X_3,X_4\}$

Przy czym akceptujące są stany zawierające $X 4$ , stan startowy to zaś ${S}$ . Jedynym co choć trochę ogranicza liczbę stanów jest to, że stan $S$ jest zawsze osiągalny, więc nie musimy uwględniać zbiorów stanów nie zawierających $S$ .

Sprawdźmy tym automatem słowo $0101000$ :

$\{S\} \rightarrow^0 \{S\} \rightarrow^1 \{S,X_1\} \rightarrow^0 \{S,X_2\} \rightarrow^1 \{S,X_1,X_3\} \rightarrow^0 \{S,X_2,X_4\} \rightarrow^0 \{S,X_3\} \rightarrow^0 \{S,X_4\}$

[edytuj] Wyrażenia regularne

Jeszcze jedną metodą wyrażania języków regularnych są wyrażenia regularne. Wyrażenie takie $X$ tworzy się używając:

$ε$ - oznaczającego język złożony ze słowa pustego
symboli nieterminali $x$ - oznaczających język złożony z pojedynczego nieterminala $x$
konkatenacji $X 1 X 2$ - oznacza to język złożony ze słów, które można podzielić tak, że pierwsza część należy do $X 1$ , druga zaś do $X 2$ .
alternatywy $X 1 | X 2$ - oznacza to język złożony z wszystkich słów $X 1$ oraz wszystkich słów $X 2$
gwiazdki $X *$ - oznacza to język złożony ze słów, które można podzielić na 0 lub więcej fragmentów, z których każdy należy do $X$

Każde wyrażenie regularne generuje język regularny i każdy język regularny można zapisać za pomocą wyrażenia regularnego.

Wiele innych wygodnych symboli można łatwo zdefiniować używając powyższych:

plus (jedno lub więcej wystąpień) - $X + = X X *$
znak zapytania (wystąpienie opcjonalne) - $X ? = X | ε$
n-krotne wystąpienie - $X^{n} = X X^{n-1} = \cdots$
od n do m wystąpień - $X^{n,m} = X^n X^{0,m-n} = X^n X? X^{0,m-n-1} = \cdots$

Inne są możliwe do emulacji, jednak nie ma na to łatwych wzorów, np. przecięcie.

Uwaga: używane w praktyce tzw. wyrażenia regularne w rzeczywistości posiadają zwykle dodatkowe możliwości, i generują więcej języków niż tylko języki regularne.

[edytuj] Twierdzenie Myhilla-Nerode'a

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

[edytuj] Przykład

Weźmy język słów o parzystej ilości jedynek i nieparzystej ilości zer. Język ten jest regularny, i prefiksy można pogrupować w 4 klasy:

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

[edytuj] Przykład (2)

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

Weźmy ciąg $p k$ prefiksów postaci $a k$ , dla kolejnych $k$ . $b j$ należy do zbioru $S k$ poprawnych sufiksów dla prefiksu $p k$ wtedy i tylko wtedy, gdy $a k b j$ należy do tego języka, a więc gdy $k = j$ . 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.

[edytuj] Lemat o pompowaniu

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

[edytuj] Przykład

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

Weźmy słowo należące do tego języka $a n b n$ , gdzie $n$ jest większe od stałej z lematu. Możliwe są trzy podziały słowa:

$y$ leży w całości w części $a$ . Wtedy $x y 2 z$ miałoby więcej znaków $a$ niż $b$
$y$ leży w całości w części $b$ . Wtedy $x y 2 z$ miałoby więcej znaków $b$ niż $a$
$y$ leży częściowo w części $a$ , a częściowo w $b$ i ma postać $a j b k$ , dla $j$ i $k$ mniejszych od $n$ i większych od zera. Wtedy $x y 2 z$ ma postać $a n - j a j b k a j b k b n - k = a n b k a j b n$ , czyli słowo nie należy do języka $\{a^nb^n : n\in N\}$ .

Czyli słowa tego nie da się podzielić, a więc język taki nie jest regularny.

Kategoria: Języki formalne

We provide Linux to the World

Język regularny

Z Wikipedii

Spis treści

[edytuj] Gramatyka regularna

[edytuj] Przykładowe języki regularne

[edytuj] Operacje na językach regularnych

[edytuj] Deterministyczne automaty skończone (DFA)

[edytuj] Przykład automatu deterministycznego

[edytuj] Przykład automatu deterministycznego (2)

[edytuj] Przykład automatu deterministycznego (3)

[edytuj] Niedeterministyczne automaty skończone (NFA)

[edytuj] Przykład

[edytuj] Konwersja NFA do DFA

[edytuj] Przykład konwersji

[edytuj] Wyrażenia regularne

[edytuj] Twierdzenie Myhilla-Nerode'a

[edytuj] Przykład

[edytuj] Przykład (2)

[edytuj] Lemat o pompowaniu

[edytuj] Przykład

Views

nawigacja

zmiany

dla edytorów

Szukaj

W innych językach