Automat permutacyjny

W teorii automatów automat permutacyjny lub automat czysto grupowy jest deterministycznym automatem skończonym, takim, że każdy symbol wejściowy permutuje zbiór stanów.

₀₀ Formalnie deterministyczny automat skończony A może być zdefiniowany przez krotkę ( Q , Σ, δ, q , F ), gdzie Q jest zbiorem stanów automatu, Σ jest zbiorem symboli wejściowych, δ jest funkcją przejścia , która przenosi stan q i symbol wejściowy x do nowego stanu δ( q , x ), q jest stanem początkowym automatu, a F jest zbiorem akceptujących stanów (też: stanów końcowych) automat. A jest automatem permutacyjnym wtedy i tylko wtedy, gdy dla każdych dwóch różnych stanów q _i i q _j w Q i każdego symbolu wejściowego x w Σ, δ( q _i , x ) ≠ δ ( q _j , x ).

Język formalny jest językiem p-regularnym (też: językiem czysto grupowym ), jeśli jest akceptowany przez automat permutacyjny. Na przykład zbiór łańcuchów o parzystej długości tworzy język p-regularny: może być akceptowany przez automat permutacyjny z dwoma stanami, w których każde przejście zastępuje jeden stan drugim.

Aplikacje

Języki czystogrupowe były pierwszą interesującą rodziną języków regularnych, dla których problem wysokości gwiazdy okazał się obliczalny .

Innym problemem matematycznym w językach regularnych jest problem oddzielania słów , w którym pyta się o rozmiar najmniejszego deterministycznego automatu skończonego, który rozróżnia dwa dane słowa o długości co najwyżej n - akceptując jedno słowo i odrzucając drugie. Znana górna granica w ogólnym przypadku to ${\ Displaystyle O (n ^ {2/5} (\ log n) ^ {3/5})}$ . Problem został później zbadany pod kątem ograniczenia do automatów permutacyjnych. W tym przypadku znana górna granica zmienia się na ${\ Displaystyle O (n ^ {1/2})}$ .