DFA lub NFA odczytuje ciąg wejściowy z pojedynczą głowicą, przesuwając się od lewej do prawej. Naturalne wydaje się zastanawianie się nad maszynami o skończonym stanie, które mają wiele głowic , z których każda porusza się po wejściu od lewej do prawej, ale niekoniecznie w tym samym miejscu na wejściu, co inne.
Zdefiniujmy maszynę skończoną za pomocą głosi w następujący sposób:
K-head NFA jest krotką, gdzie:
Jak zwykle, jest skończonym zbiorem stanów, jest skończonym alfabetem, jest stanem początkowym, oraz jest zbiorem stanów akceptujących. Pozwolić oznacza zestaw znaków, w tym pusty ciąg znaków.
to relacja przejścia: przejście oznacza, że jeśli maszyna jest w stanie , może czytać takie, że jest następną postacią dla głowy (lub jeśli ta głowa się nie porusza), a następnie przejdź do stanu .
Uruchomienie tego rodzaju maszyny (dowolna ścieżka zaczynająca się od stanu początkowego i kończąca się stanem akceptującym) powoduje nie jeden ciąg, ale różne ciągi znaków (utworzone przez połączenie znaków podczas biegu). Następnie mówimy, że przebieg jest ważny, jeśli ciągi są identyczne.
Język maszyny jest zbiorem ciągów tak, że istnieje poprawny przebieg komputera, na którym ciągi utworzone wzdłuż tego przebiegu są równe .
Pytanie: Jaką klasę języków rozpoznają takie maszyny? Czy zostało to zbadane?
Pierwszą obserwacją jest to, że takie maszyny produkują klasę większą niż zwykłe języki. Na przykład język
(Tutaj krawędź oznaczona oznacza przejście formy .)
Drugim spostrzeżeniem jest jednak to, że nie wszystkie języki kontekstowe są rozpoznawane; na przykład wydaje się, że język Dyck nie jest przez nich rozpoznawany-głowe maszyny.