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?
5
A
Odpowiedz
2
Nie, chyba że P = NP. Gdybyś miał taki algorytm, mógłbyś trywialnie zdecydować, czy dwa NFA były izomorficzne (wystarczy sprawdzić, czy A jest nadzbiorem B, a B jest nadzbiorem A), który jest known NP-hard problem. Aby uzyskać więcej informacji, read this paper. Ma ładną, zniechęcającą tabelę złożonych wyników.
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. –