Czy istnieją inne sposoby opisywania języków formalnych inne niż gramatyka?

Szukam teorii matematycznych, które zajmują się opisywaniem języków formalnych (zestawu ciągów) w ogólności, a nie tylko hierarchii gramatycznej.

Istnieje wiele możliwości. Inni wspominali już o automatach, które oferują bogaty wybór. Weź również pod uwagę następujące ramy:

1. Niektóre języki można zdefiniować bezpośrednio za pomocą (ko) definicji indukcyjnych . Na przykład najmniejszy punkt stały
   jest tym samym językiem, co opisany przez(ba∣a)∗, największy punkt stały to(ba∣a)ω. Zauważ, że taką definicję można również zapisać w postaci rachunku różniczkowego lubreguły wnioskowania:$\qquad \begin{align*} \phantom{a} \\ &\phantom{\Rightarrow}\ \varepsilon \in L \\ w \in L &\Rightarrow aw \in L \\ aw \in L &\Rightarrow baw \in L \\ \phantom{a} \end{align*}$
   $(ba\mid a)^*$$(ba\mid a)^\omega$
   $\qquad \begin{align*} \phantom{a}\\ \frac{}{\varepsilon}, \quad \frac{w}{aw}, \quad \frac{aw}{baw} \\ \phantom{a} \end{align*}$

2. Słowa definiują struktury słów, które można wykorzystać jako modele formuły logicznej . Zasadniczo, każde słowo określa domenę do pozycji , predykaty P : D → { 0 , 1 } , tak że P ( I ) ⟺ W I = dla każdego z ∈ Ď , predykat <, który jest < z $D_w = \{1, \dots, n\}$$P_a : D \to \{0,1\}$$P_a(i) \Longleftrightarrow w_i = a$$a \in \Sigma$$<$$<$$\mathbb{N}$ograniczone do i predykatu suc : D w × D w → { 0 , 1 }, co jest prawdą wtedy i tylko wtedy, gdy drugi parametr jest bezpośrednim następcą pięści. Tak na przykład, gdy w = b b a a b a następnie$D_w$$\operatorname{suc} : D_w \times D_w \to \{0,1\}$
   $w = aababaab$
   w rzeczywistości taformuła pierwszego rzędudefiniuje --- poprzez zestaw wszystkich struktur słów, które ją spełniają --- ten sam język, co(ba∣a)∗. Odpowiednijęzykω(ba∣a)ωjest opisanywzorem LTL$\qquad \begin{align*} \phantom{a}\\ S_w \models \forall\, i. \forall\, j.\ (P_b(i)\ \land\ \operatorname{suc}(i,j)) \to \lnot P_b(j); \\ \phantom{a} \end{align*}$
   $(ba\mid a)^*$$\omega$$(ba\mid a)^\omega$
   Znanych jest kilka równoważności klasycznych klas językowych i niektórych logik. Na przykładFOodpowiada językom bez gwiazd, słabyMSOdo zwykłych języków, aMSOdojęzykówω-regularnych. Zobacztutajdla odniesienia.$\qquad \begin{align*} \phantom{a}\\ \square\,(P_b \to\bigcirc(\lnot P_b)) \\ \phantom{a} \end{align*}$
   $\omega$

3. Coś prostopadłego do klasycznych klas to języki wzorcowe . Załóżmy, że końcowy alfabet i zmienny alfabet X = { x 1 , x 2 , … } . Ciąg p ∈ ( Σ ∪ X ) + nazywa się wzorem . Niech H = { σ ∣ σ : X → Σ ∗ } zbiór podstawień. Definiujemy język wzorca p jako$\Sigma$$X=\{x_1, x_2,\dots\}$$p \in (\Sigma \cup X)^+$$\mathcal{H}= \{\sigma \mid \sigma : X \to \Sigma^*\}$$p$
   Zauważ, żeσjest przedłużony do pracy nad wzorami; symbole terminali pozostają niezmienione. Jako przykład rozważmyL(x1abbax1)={wabbaw∣w∈{a,b}∗}.$\qquad \begin{align*} \phantom{a}\\ \mathcal{L}(p) = \{\sigma(p) \mid \sigma \in \mathcal{H}\}. \\ \phantom{a} \end{align*}$
   $\sigma$
   $\mathcal{L}(x_1abbax_1)= \{wabbaw\mid w \in \{a,b\}^*\}$
   Zauważ, że zezwalamy na podstawienia do usuwania zmiennych; niektóre właściwości klasy języków wzorcowych są bardzo różne w przypadku usuwania w porównaniu do nieusuwalnych podstawień. Języki wzorcowe są szczególnie interesujące w nauce w stylu złotym .

Powinieneś spojrzeć na teorię automatów . Jest w tym mnóstwo materiału.

Na przykład, możesz zdefiniować zwykły język z niedeterministycznym automatem skończonym z oznaczonymi krawędziami: łańcuch należy do języka, jeśli automat może podążać za przejściami oznaczonymi jego znakami i zatrzymuje się w stanie końcowym.

Również gramatyka bezkontekstowa może być rozpoznawana przez automat pushdown .

Innym sposobem definiowania języków są maszyny Turinga .

W hierarchii Chomsky'ego istnieją cztery rodzaje języków formalnych (każdy z nich jest podzbiorem następujących po nim):

Język regularny formalny można opisać:

1. Gramatyka regularna
2. Automat skończony (deterministyczny / niedeterministyczny)
3. Wyrażenie regularne

1., 2. i 3. są równoważne i z jednego z nich możesz zbudować pozostałe.

Bezkontekstowych formalny język może być opisana przez:

1. Gramatyka bezkontekstowa
2. Automat pushdown

Również 1. i 2. są równoważne.

Kontekstowa formalny język może być opisana przez:

1. Automat związany liniowo (maszyna Turinga z ograniczoną taśmą)

Rekurencyjnie przeliczalny język formalny można opisać:

1. Całkowita maszyna Turinga

Oprócz innych odpowiedzi można opisać i sklasyfikować języki pod względem „generatorów” i właściwości zamknięcia. Na przykład sensowne jest mówienie o najmniejszym AFL generowanym przez jakiś język. Dobrym miejscem do rozpoczęcia nauki o tego rodzaju opisach jest ta książka, chociaż znalezienie jej twardej kopii może być dość trudne.