Język regularny

Język regularny – język formalny taki, że istnieje deterministyczny automat skończony potrafiący zdecydować, czy dane słowo należy do języka. Równoważnie, taki, że istnieje dlań gramatyka regularna. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 3.

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.

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

Nie są zaś nimi na przykład:
  (dopuszczalne w gramatykach bezkontekstowych)
  (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:
 zbiór wszystkich słów alfabetu 
 zbiór wszystkich słów alfabetu  o długości 
 zbiór wszystkich słów alfabetu  o parzystej długości
 zbiór wszystkich słów alfabetu  zaczynających się od zera
 zbiór wszystkich słów alfabetu  nie zaczynających się od zera
 zbiór wszystkich słów alfabetu  w których na przemian występują zera i jedynki
 zbiór wszystkich słów alfabetu  w których na przemian występują zera, jedynki i dwójki

Zbiór wszystkich języków regularnych oznacza się przez

Operacje na językach regularnych 
Języki regularne są zamknięte ze względu na operacje:
 dopełnienia
 np. 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
 sumy
 np. 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ęcia
 np. 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
 odbicia lustrzanego („transpozycji”, tzn. słowa z tego języka, tyle, że zapisane 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
 konkatenacji
 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
 domknięcia Kleene’ego
 np. język składający się tylko z 0 i 1 po zastosowaniu domknięcia Kleene’ego jest językiem wszystkich słów zero-jedynkowych.

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.

Rodzinę języków rozpoznawalnych przez automaty skończone oznacza się przez

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.

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.

Przykład automatu deterministycznego (3) 
Automat służący do sprawdzania czy dane słowo binarne ma  lub   znaków mógłby wyglądać tak:
 Stany to    aż do  i stan ZaDługie.
 Stan początkowy to 
 Jeśli automat jest w stanie   to po przeczytaniu dowolnego znaku przechodzi w stan 
 Jeśli automat jest w stanie  to po przeczytaniu dowolnego znaku przechodzi w stan ZaDługie.
 Jeśli automat jest w stanie ZaDługie, po przeczytaniu dowolnego znaku pozostaje w stanie ZaDługie.
 Akceptujące są stany  i

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

Główną konsekwencją tego dowodu jest, wspomniana już wcześniej, bezpośrednia zależność języków regularnych i automatów skończonych. Zatem dla każdego języka regularnego można stworzyć automat skończony i, analogicznie, każdy automat skończony rozpoznaje język regularny.

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.

Przykład 
Weźmy NFA rozpoznające język słów nad alfabetem binarnym, których czwartym od końca znakiem jest 1:
 
 
  – jedynym niedeterministycznym przejściem jest przejście ze stanu  po przeczytaniu jedynki, albo w  albo w 
 
 
 
 
 
 
 
 
 Stan startowy to  stanem akceptującym jest 

Możemy uruchomić ten automat na słowie 
 

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

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

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.

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:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Sprawdźmy tym automatem słowo

Wyrażenia regularne 
Jeszcze jedną metodą wyrażania języków regularnych są wyrażenia regularne. Wyrażenie takie  tworzy się używając:
  – oznaczającego język złożony ze słowa pustego,
 symboli nieterminali  – oznaczających język złożony z pojedynczego nieterminala 
 konkatenacji  – oznacza to język złożony ze słów, które można podzielić tak, że pierwsza część należy do  druga zaś do 
 alternatywy  – oznacza to język złożony z wszystkich słów  oraz wszystkich słów 
 gwiazdki  – 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 

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ń) – 
 znak zapytania (wystąpienie opcjonalne) – 
 n-krotne wystąpienie – 
 od n do m wystąpień – 

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.

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

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.

Przykład (2) 
Weźmy język  czyli wszystkich słów składających się z  znaków  po których występuje  znaków  dla dowolnego 

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

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

Przykład 
Weźmy język  czyli wszystkich słów składających się z  znaków  po których występuje  znaków  dla dowolnego  naturalnego.

Weźmy słowo  gdzie  jest większe od stałej  z lematu o pompowaniu. Wobec warunku  z lematu,  leży w całości w części  Wtedy  ma więcej znaków  niż  gdyż  Zatem słowo  nie należy do  wbrew tezie lematu o pompowaniu.

Ponieważ  nie spełnia lematu o pompowaniu, to nie jest regularny.

Języki formalne