Różnica między wyrażeniem regularnym a gramatyką w automatach

Jestem nowy w automatach. Krótkie wprowadzenie do wyrażeń regularnych otrzymałem wczoraj. Przeczytałem różne reguły definiujące wyrażenie regularne. Ale nie jestem w stanie odróżnić wyrażeń regularnych od gramatyki języka (nie uczono mnie gramatyki wyrażeń regularnych).

Rozumiem, że gramatyka pomaga nam generować poprawne ciągi w języku, ale wtedy właśnie takie są reguły definiowania wyrażeń regularnych. Więc gdzie leży różnica? Zapytałem mojego profesora, który powiedział, że wyrażenia regularne są najbardziej podstawowymi ciągami w języku, a gramatyka to zbiór reguł dla każdego języka, które są wyższego rzędu niż wyrażenie regularne. Czy ktoś może podać bardziej szczegółowe informacje?

Wyrażenia regularne, gramatyka regularna i automaty skończone to po prostu trzy różne formalizacje tego samego. Istnieją algorytmy do konwersji z dowolnego z nich na dowolny inny.

Podstawowym powodem, dla którego mamy wszystkie trzy, jest to, że zostały stworzone niezależnie, z pierwszym zestawem równoważności (istnieje również kilka innych formalizmów) udowodnionym przez Kleene (ten wynik lub jego część nazywamy Twierdzeniem Kleene'a).

W tym kontekście, w zależności od tego, w którą stronę chcesz uruchomić modele, wszystkie one rozpoznają lub generują ciągi zwykłego języka, a matematycznie w tym sensie nie ma różnicy.

Oczywiście czasami jeden model jest łatwiejszy w użyciu niż inny do określonego zadania, ze względu na szczegóły formalizmu. Ponadto sposób, w jaki działają w ludzkiej głowie, jest często nieco inny, skończone automaty „czują się” jak komputery, wyrażenia regularne „czują się”, jakbyś tworzył ciąg z mniejszych podciągów, a gramatyka regularna „czuje się” jak bardziej tradycyjna gramatyka wyprowadzenie lub klasyfikacja zdania w języku (co nie jest zaskoczeniem, gdy spojrzysz na historię).

Aby porównać oba, zdefiniujmy je:

Wyrażenia regularne

Wyrażenia regularne są więc rekurencyjnie zdefiniowane w następujący sposób:

1. $\emptyset$
2. $\varepsilon$
3. $a$$a \in \Sigma$
4. $A$$B$
   • $A\cdot B$
   • $A \mid B$
   • $A^{\ast}$

Wraz z pewną semantyką (tj. Jak interpretujemy operatory w celu uzyskania łańcucha), otrzymujemy sposób generowania łańcuchów z normalnego języka.

Gramatyki regularne

$(N,\Sigma, P, S \in N)$$N$$\Sigma$$S$$P$$\Sigma^{\ast}$$P$

Właściwe gramatyki liniowe

$B$$C$$a$$\varepsilon$

1. $B \rightarrow a$
2. $B \rightarrow aC$
3. $B \rightarrow \varepsilon$

Lewa gramatyka liniowa

$B \rightarrow Ca$

Rzeczy do przemyślenia

Patrząc na te definicje i grając z nimi, widzimy, że wyrażenia regularne wyglądają jak pasujące reguły lub sposoby radzenia sobie z ciągami znaków naraz.

$S$

Jednak tak naprawdę robią to samo fundamentalne rzeczy, a to, jak postrzegasz metaforę ich funkcji, zależy od ciebie.