Język regularny - Polski Serwis Naukowy

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. Równoważnie, taki, że istnieje dlań gramatyka regularna.

Wszystkie języki regularne są bezkontekstowe.

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.

Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana.
Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.

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.

Przykładowe języki regularne

Regularnymi są np. języki:

Język bezkontekstowy (ang. context-free language) to język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa.
Symbol nieterminalny – w gramatyce formalnej symbol, który można definiować. Symbole nieterminalne zwane są również zmiennymi syntaktycznymi, ponieważ umożliwiają tworzenie ciągów zawierających kombinacje symboli terminalnych i nieterminalnych.

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

Zbiór wszystkich języków regularnych oznacza sie przez $REG$ .

Deterministyczny automat skończony (ang. Deterministic Finite-state Automaton, DFA) to abstrakcyjna maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa, po przeczytaniu każdego zmieniając swój stan na stan będący wartością funkcji jednego przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), słowo należy do języka regularnego, do rozpoznawania którego jest zbudowana.
Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) - maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe), mówimy że automat akceptuje czytane słowo.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)