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?

— Lamine
źródło

Czy algorytm Djikstry nie powinien załatwić sprawy? (Prawdopodobnie coś tu źle

— rozumiem

„co najwyżej długość

k

$k$ „?

— alpoge

Nie ma za co, Kaveh. Tak, zapomniałem „co najwyżej”, edytowałem ponownie.

— Lamine,

Odpowiedź jest prosta - czy to pytanie do pracy domowej?

— Sariel Har-Peled

Czy mamy dostęp do opisu automatów, czy mamy go tylko jako czarną skrzynkę?

— Raphael

Odpowiedzi:

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$

— Yuval Filmus
źródło

Myślę też, że transformacja PDA CFG jest wielomianowa. Dzięki! Więc problem jest w .

\to

$\rightarrow$

P

$P$

— Lamine

Ok, ponieważ istnieje sposób na bezpośrednie obliczenie najniższej długości,nie jest wejściem. Ale nie rozumiem, po co zastępować wszystkie terminale stałym. Algorytm powinien działać poprawnie z oryginalnymi terminalami.

| k |

$|k|$

— Lamine

Masz rację, to właściwie nie ma znaczenia.

— Yuval Filmus

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

— Sariel Har-Peled
źródło

Nie, nie jestem studentką. Problem, o którym wspomniałem, jest początkowo problemem sieciowym, który jest modelowany jako automat. Po prostu wiedziałbym, czy warto szukać rozwiązania wielomianowego, czy nie.

— Lamine,

Czy ta odpowiedź nie powinna być komentarzem?

— Oleksandr Bondarenko

Tak, powinno. Sariel, czy możesz przenieść to do komentarza lub udzielić odpowiedzi?

— Suresh Venkat

@Suresh: Być może zdajesz sobie z tego sprawę, ale teraz moderatorzy mogą zamienić odpowiedź w komentarz .

— Tsuyoshi Ito

Pierwszą odpowiedź przeniosłem na komentarz. To jest nowa odpowiedź.

— Suresh Venkat

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

— alpoge
źródło

(ale zdecydowanie

— wielogodzinny

Nie jestem pewien, czy algorytm Dijkstry może rozwiązać problem. Może znaleźć najkrótszą ścieżkę między stanem początkowym a końcowym. Oczywiście można wygenerować słowo, które można zaakceptować tymi ścieżkami. Ale te ścieżki są elementarne, a słowa można przyjmować ścieżkami nieelementowymi; w przeciwnym razie problem ustalenia, czy gramatyka bezkontekstowa może wygenerować dowolne słowo, byłby rozstrzygalny, ale tak nie jest.

— Lamine,

Testy pustki dla świetlówek kompaktowych są rozstrzygalne, prawda?

— alpoge

(Wybacz mi jeszcze raz, jeśli się mylę!)

— alpoge 20.01.11

Cóż, można to zrobić za pomocą algorytmu „oznaczania” (biorąc pod uwagę CFG) - oznaczanie zacisków, następnie oznaczanie rzeczy, które wyprowadzają zaciski, następnie oznaczanie rzeczy, które wyprowadzają oznaczone, itp., Aż do zakończenia procesu, a następnie sprawdzanie jeśli zmienna początkowa jest zaznaczona. Zignoruj też moją odpowiedź - właśnie to powinieneś zrobić dla NFA (na pewno nie dla PDA!).

— alpoge