2
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 Rudoya, tutaj poniżej) : Można to zrobić w czasie …