Pytania otagowane jako synchronization

Status przypuszczenia Cerny'ego?

DFA ma słowo synchronizujące, jeśli istnieje ciąg znaków, który wysyła dowolny stan DFA do jednego stanu. W „The Cerny Conjecture for Aperiodic Automata” AN Trahtmana (Discrete Mathematics and Theoretical Computer Science vol. 9: 2, 2007, s. 3–10) napisał: Cerny przypuszczał w 1964 r., Że każdy DFA synchronizowany w stanie n …

19 fl.formal-languages automata-theory open-problem synchronization

Liczba stanów automatów lokalnych

Automat deterministyczny nazywa się k -lokalny dla k > 0, jeżeli dla każdego w ∈ X k zbiór { δ ( q , w ) : q ∈ Q } zawiera co najwyżej jeden element. Intuicyjnie oznacza to, że jeśli słowo w o długości k prowadzi do stanu, to ten …

10 fl.formal-languages automata-theory synchronization

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.