Trudność ze znalezieniem co najwyżej słowa

Opis problemu:

Pozwolić $M$ być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól $\cal A$być jego alfabetem wejściowym. Czy jest jakieś słowo?$w \in \cal A^*$ św $|w| \leq k$ które jest akceptowane przez $M$ ?

Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?

Oblicz przecięcie swojego języka CFG ze zwykłym językiem $\sum_{i=0}^k A^k$ (odpowiada to pomnożeniu liczby stanów przez $k$i dodanie stanu „ślepego zaułka”). Teraz sprawdź, czy wynik jest pusty: przekonwertuj na gramatykę (myślę, że wynik będzie miał wielomian) i „cofnij” z produkcji epsilon.

Edycja: Kaveh wspomniał, że jest to wielomian w $k$, więc jeśli $k$ jest podany jako dane wejściowe, algorytm wykładniczy $|k|$. Jednak Kaveh znalazł sposób, aby to naprawić. Przekształć oryginalny automat w CFG i zastąp wszystkie terminale stałym terminalem. Teraz użyj algorytmu iteracyjnego, aby znaleźć minimalny rozmiar słowa generowanego przez każdy nieterminalny, w następujący sposób.

Zainicjuj wszystkie długości za pomocą $\infty$, a następnie iteracyjnie aktualizuj wszystkie długości w oczywisty sposób: biorąc pod uwagę produkcję $A \rightarrow a^t \prod B_i$ (kolejność nie ma znaczenia) $f(A) = \min(f(A),t+\sum f(B_i))$. Twierdzenie: zbiega się w iteracjach , gdzie jest liczbą nieterminalnych. Powodem jest to, że w drzewie generującym słowo o minimalnej długości żaden terminał nie jest używany dwukrotnie; każda „krawędź” wymaga przetworzenia co najwyżej jednej iteracji (niektóre krawędzie mogą być „aktualizowane” równolegle).$O(n)$$n$

Zmień wszystkie znaki alfabetu na jeden określony znak. Teraz masz zdefiniowany PDA dla pojedynczego znaku. Jego językiem jest gramatyka bezkontekstowa. Jednak gramatyka bezkontekstowa nad jednym znakiem jest regularna. Tak więc przekonwertuj CFG na zwykły język, a następnie sprawdź, czy zawiera słowo długości k.

Teraz wszystkie te konwersje zwykle wymagają czasu wykładniczego, ale wydaje mi się mało prawdopodobne, że problem jest NP całkowity. Zwłaszcza jeśli dopuścisz czas wielomianowy w .$k$

Mogę się mylić i przepraszam za moją początkową krótką odpowiedź ...

BTW, fakt, że CFG na pojedynczą literę jest regularny, wynika z twierdzenia Parikha. Chociaż bezpośredni dowód nie jest zbyt trudny. Zobacz link, aby uzyskać więcej szczegółów na temat twierdzenia Parikha - to piękny wynik ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Prawdopodobnie nieoptymalna metoda: uruchom algorytm Djikstry. Następnie dla każdego stanu końcowego porównaj odległości z . Jeśli jakieś są , zaakceptuj. Odrzucać.$k$$\leq k$

EDYCJA: Powyższe działa tylko dla NFA! Przepraszam za to.