Jakie języki są rozpoznawane przez maszyny z jednym licznikiem?

Maszyny liczące z dwoma lub więcej licznikami są zwykle pokazywane jako równoważne maszynom Turinga w kursach teorii teorii obliczeń. Jednak nie widziałem formalnej analizy tego, które języki mogą być rozpoznawane przez maszynę z jednym kontem. Czy te języki są równoważne z językami bezkontekstowymi (być może przez jakąś sprytną konstrukcję odnoszącą je do PDA), czy też są zupełnie inną klasą języków?

Automaty z jednym licznikiem to automaty wypychające z tylko jednym symbolem dozwolonym na stosie (plus stały symbol dolny). Języki rozpoznawane przez jeden automat licznika tworzą właściwy podzbiór języków bezkontekstowych.

Na przykład automaty z 1 licznikiem mogą rozpoznać język który nie jest regularny, ale nie mogą rozpoznać języka { a n b m a m b n }, który jest pozbawiony kontekstu i może zostać rozpoznany przez 2 liczniki automaty też.$\{a^nb^n\}$$\{a^nb^ma^mb^n\}$

Jeśli k-DCA jest deterministycznym automatem k-licznika , a k-NCA jest niedeterministycznym automatem k-licznika, mamy następujące właściwe wtrącenia:

DFA (zwykłe języki) 1-DCA ⊂ 2-DCA$\subset$$\subset$

1-DCA 1-NCA$\subset$

Jeśli nie zezwalamy na przejścia (przejście na czas rzeczywisty ), wówczas k-DCA ⊂ k'-DCA dla k <k '.$\epsilon$$\subset$

$\geq$$\{ww^R\}$$\{a^nb^nc^n\}$

Automaty do liczenia były badane w starożytnej przeszłości języka formalnego w kontekście teorii AFA i AFL (abstrakcyjne rodziny automatów i języków) przez zespoły amerykańskie i francuskie (Ginsberg, Greibach, ..., Nivat, Berstel, ...)

Automaty liczników są zazwyczaj definiowane jako automaty stanów skończonych wyposażone w pamięć zewnętrzną, składające się z liczby naturalnej (lub kilku, jeśli masz więcej niż jeden licznik). Liczba ta może być zwiększana, zmniejszana i (zwykle) testowana na zero. Obliczenia rozpoczynają się od zera i są akceptowane tylko wtedy, gdy licznik ma na końcu zero, co jest porównywalne z akceptacją pustego stosu w dół

Jeśli taka maszyna ma co najmniej dwa takie liczniki, to jest ona równoważna maszynie Turinga, nawet w przypadku deterministycznym. Dowodem na to jest Minsky i można go znaleźć w linkowanym artykule na Wikipedii. Model jest oczywiście związany z maszyną rejestrującą wymienioną na tej samej stronie wikipedii. Problemy z kodowaniem wspomniane w artykule na Wikipedii nie są tutaj ważne, ponieważ rozważamy automaty z taśmą wejściową (w końcu musimy odczytać ciąg wejściowy), podczas gdy wikipedia na tej stronie zakłada tylko liczniki.

Ten licznik automat może być postrzegany jako specjalny typ pda, posiadający tylko jeden symbol stosu i dolną część stosu (który nigdy nie jest przenoszony). Umożliwia to automatowi sprawdzenie, czy licznik / stos ma wartość zero, i odpowiednie działanie.

Istnieją trzy typy automatów liczących. Więc mądrze łącz wyniki, w przeciwnym razie skończysz z sprzecznościami (jak zdarzyło mi się w przeszłości). Wszystkie trzy typy są (ściśle) zawarte w językach bezkontekstowych dla jednego licznika.

Powyższy typ przechowuje liczbę całkowitą (lub liczbę naturalną, co nie ma znaczenia) i może przetestować jej zawartość od zera. Blind sklep licznik automaty liczbą całkowitą, ale nie może test na zero. Mogą jednak zliczyć poniżej zera. Częściowo zaślepione automaty liczników nie mogą testować zera, ale przechowują liczbę naturalną. Jeśli maszyna próbuje spaść poniżej zera, zatrzymuje się bez akceptacji. Jest to naturalny rodzaj przechowywania do modelowania sieci Petriego. Jest on także powiązany z PDA, teraz z jednym symbolem stosu bez specjalnego dolnego znacznika (i stąd problem testowania na zero: po prostu utkniemy, gdy pękamy ostatni element stosu). Czasami nazwy rodzin zdefiniowanych przez modele liczników reaktywnych to OCL, ROCL i 1-BLIND.

$(Dc)^*$$D = \{ w\in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$$a$$b$$c$

Jako przykład odpowiednich badań Latteux etal opublikował nietrywialną pracę „Rodzina języków jednokryterialnych jest zamknięta pod ilorazem” (która tak naprawdę dotyczy ROCL).