Pytania oznaczone «nfa»

Czy dany język regularny zawiera nieskończony podzbiór bez prefiksów?

Zestaw słów nad skończonym alfabetem nie zawiera prefiksu, jeśli nie ma dwóch odrębnych słów, w których jedno jest prefiksem drugiego. Pytanie brzmi: Jaka jest złożoność sprawdzania, czy zwykły język podany jako NFA zawiera nieskończony podzbiór bez prefiksów? Odpowiedź (z powodu Michaiła...

Z jaką klasą języków są rozpoznawane automaty skończone

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...