Czy badane jest następujące rozszerzenie automatów skończonych?

Rozważmy maszynę skończoną jak zwykle, ale przy każdym przejściu może ona także aktualizować licznik liczb całkowitych, dodając lub odejmując liczbę. Powiedzmy, funkcja przejścia w postaci $\delta(q,a) = (p,k)$ przechodzi do nowego stanu $p$ i dodaje $k$ do licznika, gdzie$k \in \mathbb{Z}$ (więc może być dodatnia, ujemna lub zero).$k$

Łańcuch jest akceptowany, jeśli stan końcowy i wartość licznika są w , gdzie jest skończonym zestawem par stanów i wartości licznika.$F$$F$

Czy ten model jest znany? Nie mogłem znaleźć żadnego odniesienia do tego konkretnego rozszerzenia.

Zakładając, że może być dowolną liczbą całkowitą, wówczas można to sformalizować jako ślepy automat z jednym licznikiem . Zazwyczaj te automaty akceptują stan końcowy, gdy jego licznik wynosi zero, ale możemy łatwo modelować typ akceptacji, jeśli zezwolisz na przejścia ϵ (które nie zużywają danych wejściowych). Jeśli się nie mylę, jak w przypadku automatów skończonych, można się pozbyć ϵ , ale to nie jest trywialny wynik.$k$$\epsilon$$\epsilon$

Istnieje kilka rodzajów automatów jednego licznika. W najbardziej ogólnej formie mogą oni sprawdzić, czy wartość licznika jest równa zero. Języki, które akceptują, są ścisłym podzbiorem języków bezkontekstowych.

Model, którego prawdopodobnie szukasz, nazywa się ślepy , nie może przetestować na zero, z wyjątkiem ostatniego testu akceptacji na końcu obliczeń.

Ten model jest wariantem ważonych automatów, które są szeroko badane (chociaż jest wiele otwartych pytań na ich temat). Możesz zacząć tutaj: Podręcznik ważonych automatów .

Zauważ, że czasami są one nazywane „automatami odległości” (chociaż staje się to coraz mniej powszechne).