Czym jest język regularny?

W kontekście informatyki, słowo jest konkatenacją symboli . Używane symbole nazywane są alfabetem . Na przykład niektóre słowa utworzone z alfabetu {0,1,2,3,4,5,6,7,8,9} byłyby 1, 2, 12, 543, 1000, i 002.

Język jest wtedy podzbiorem wszystkich możliwych słów. Na przykład, możemy chcieć zdefiniować język, który przechwytuje wszystkich elitarnych agentów MI6. Wszystkie zaczynają się od podwójnego-0, więc słowa w języku be 007, 001, 005, i 0012, ale nie 07 czy 15. Dla uproszczenia mówimy, że język jest "nad alfabetem" zamiast "podzbiorem słów utworzonym przez konkatenację symboli w alfabecie".

W informatyce chcemy teraz klasyfikować języki. Język nazywamy regularnym , jeśli można zdecydować, czy słowo jest w języku z algorytmem / maszyną o stałej (skończonej) pamięci, badając wszystkie symbole w słowie jeden po kolejny. Język składający się tylko ze słowa 42 jest regularny, ponieważ można zdecydować, czy słowo znajduje się w nim bez konieczności arbitralnej ilości pamięci; wystarczy sprawdzić, czy pierwszy symbol to 4, czy drugi to 2, i czy kolejne liczby następują.

Wszystkie języki ze skończoną liczbą słów są regularne, ponieważ możemy (teoretycznie) po prostu zbudować drzewo przepływu sterowania o stałej wielkości (można je wizualizować jako zbiór zagnieżdżonych if-instrukcji, które badają jedną cyfrę po drugim). Na przykład, możemy sprawdzić, czy słowo znajduje się w języku" liczby pierwsze między 10 A 99 " z następującą konstrukcją, nie wymagającą pamięci, z wyjątkiem tej do kodowania, w której linii kodu jesteśmy obecnie: {]}

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

Zauważ, że wszystkie skończone języki są regularne, ale nie wszystkie języki regularne są skończone; nasz język double-0 zawiera nieskończoną liczbę słów (007, 008, ale także 004242 i 0012345), ale można je przetestować ze stałą pamięcią: aby sprawdzić, czy słowo należy w nim sprawdzić, czy pierwszy symbol to 0, a drugi symbol to 0. Jeśli tak jest, zaakceptuj to. Jeśli słowo jest krótsze niż trzy lub nie zaczyna się od 00, nie jest to nazwa kodowa MI6.

Formalnie, konstrukcja maszyny skończonych Stanów lub gramatyki regularnej jest używana do udowodnienia, że język jest regularny. Są one podobne do if-wypowiedzi powyżej, ale pozwalają na dowolnie długie słowa. Jeśli istnieje maszyna skończonego stanu, istnieje również regularna gramatyka i odwrotnie, więc wystarczy pokazać albo. Na przykład skończona maszyna stanowa dla naszego języka double-0 to:

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

Równoważna gramatyka regularna to:

start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...

Odpowiednikiem wyrażenia regularnego jest:

00[0-9]*

Niektóre języki są nie regularne. Na przykład język dowolnej liczby 1, po której następuje ta sama liczba 2 (często zapisywana jako 1ⁿ2ⁿ , dla dowolnego n ) nie jest regularna - potrzeba więcej niż stałej ilości pamięci(= stałej liczby stanów), aby zapisać liczbę 1 s, aby zdecydować, czy słowo jest w języku.

Powinno to być Zwykle wyjaśnione na kursie Informatyki Teoretycznej. Na szczęście Wikipedia dość ładnie wyjaśnia zarówno języki formalne, jak i języki regularne.