5
Biorąc pod uwagę dwa niedeterministyczny automat skończony M1 i M2, czy istnieje skuteczny algorytm do ustalenia, czy język akceptowany przez M1 jest rozszerzeniem języka akceptowanego przez M2?Czy istnieje skuteczny algorytm decydujący o tym, czy język zaakceptowany przez jedną NFA jest nadzbiorem języka akceptowanego przez inny?
Zastanawiam się, czy wiesz o redukcji z innego NP pełnego problemu z izomorfizmem NFA? – hugomg
@missigno: Dodałem link do papieru, który wyjaśnia nieco bardziej szczegółowo redukcje. – Mikola
Mikola, twoja odpowiedź jest poprawna, ale twoje sformułowanie jest błędne: izomorficzne oznacza "równego kształtu", dwa automaty są izomorficzne, istnieje 1-1 odwzorowanie między ich stanami, takie, że bla bla. Co nie ma tu znaczenia, dwa automaty mogą akceptować ten sam język bez izomorficzności. (To wprowadza zamieszanie w to, że sprawdzanie izomorfizmu wykresu jest również NP-trudne). Jeśli zmienisz swoją odpowiedź jako "czy dwa NFA przyjmują ten sam język" zamiast "czy dwa NFA były izomorficzne", wszystko będzie dobrze. –