Czy maszyna Turinga może zdecydować, czy NFA akceptuje ciąg znaków pierwszej klasy?

Chcę wiedzieć, czy można rozwiązać następujący problem:

Instancja: NFA A z n stanami

Pytanie: Czy istnieje jakaś liczba pierwsza p, taka, że A akceptuje pewien ciąg długości p.

Wierzę, że ten problem jest nierozstrzygalny, ale nie mogę tego udowodnić. Decydent może łatwo mieć algorytm, aby dowiedzieć się, czy określona liczba jest liczbą pierwszą, ale nie widzę, w jaki sposób byłby w stanie przeanalizować NFA wystarczająco szczegółowo, aby dokładnie wiedzieć, jakie długości może produkować. Mógłby zacząć testować łańcuchy za pomocą NFA, ale dla nieskończonego języka może się nigdy nie zatrzymać (a zatem nie decydować).

Oczywiście NFA można łatwo zmienić na DFA lub wyrażenie regularne, jeśli rozwiązanie tego potrzebuje, oczywiście.

To pytanie zastanawiam się jako samodzielnie przygotowane pytanie przygotowawcze do finału, które pojawi się za 2 tygodnie.

computability finite-automata Chłód
źródło

Nie jestem pewien, czy jest to poziom licencjacki, więc nie martw się o jego usunięcie. Może to okazać się trudnym problemem, patrz np. Terrytao.wordpress.com/2007/05/25/…

Cóż, wymyśliłem to, więc może to być trudne. Nie znalazłem żadnych dowodów nierozstrzygalnych problemów związanych z NFA / DFA, dlatego pomyślałem, że może być interesujące wypróbowanie jednego.

Uważam, że to, z czym się łączysz, to inny (łatwiejszy) problem. Może odpowiedzieć „ile ciągów długości x akceptuje NFA?”. Korzystając z podanej formuły, musielibyśmy sprawdzić nieskończenie wiele instancji aby sprawdzić, czy istnieje ciąg znaków akceptowany przez NFA, który ma długość pierwszą. Nie pytam o konkretną liczbę pierwszą, pytam o wszystkie z nich.

s_{L} (n)

$s_L(n)$

Odpowiedzi:

Długości łańcuchów akceptowane przez DFA tworzą zestaw półliniowy (jak w twierdzeniu Parikha dla języków bezkontekstowych), ich opis nie jest zbyt trudny do uzyskania (zasadniczo splatając wszystkie możliwe cykle automatu), i przez Twierdzenie Dirichleta, że dowolny postęp arytmetyczny postaci z zawiera nieskończoność liczb pierwszych. $a + b k$ $\gcd(a, b) = 1$

Połączenie powyższych elementów daje algorytm do sprawdzenia, czy Twój zwykły (a nawet pozbawiony kontekstu język) zawiera ciągi liczb pierwszych. Zdecydowanie nie jest to proste pytanie, IMVHO ...

vonbrand
źródło

Byłbym wdzięczny za pomoc w zrozumieniu twierdzenia Parikha w tym przypadku. Możemy oczywiście zmienić NFA w PDA, po prostu nie używając stosu w PDA. Czy podzbiory liniowe określają cykle? Jeśli tak, jak to działa?

Chill

@Chill, rozważ dowolną ścieżkę przez DFA. Może przejść od stanu początkowego do końcowego lub może zapętlić się. Możliwe długości łańcuchów są określone przez „część prostą” + sumę razy „długość możliwej pętli” dla dowolnych . Wystarczy narysować plątaninę DFA i prześledzić ścieżki przez nią. Zobaczysz, że możliwe długości mieszczą się w rodzinach ciągów arytmetycznych określonych przez cykle, tj. Tworzą one zestaw półliniowy. Nie musisz iść bez kontekstu (po prostu fajny darmowy bonus).

k

$k$

k

$k$

vonbrand

Myślę, że to odpowiada na moje pytanie. Spróbuję przeczytać więcej na temat twierdzenia Parikha. Rozumiem ideę tego i jak można określić cykle w tym przypadku. Chcę wymyślić bardziej praktyczne rozwiązanie, w którym tworzę rzeczywisty algorytm, aby rozwiązać ten problem.

Chill

@Chill, spójrz na mój poprzedni komentarz. Nie jest tak trudno wymyślić opis możliwych długości, po prostu usuwając symbole z DFA jako wykres i sprawdzając przejścia między stanem początkowym i końcowym. Trudne do sformalizowania, łatwe do zrozumienia ręcznie dla dowolnego podanego przykładu.

vonbrand

@dkuper, to nie jest takie proste. język jest nieskończony, ale nie zawiera ciągu liczb pierwszych.

a a a a (a a)^{*}

$a a a a (a a)^*$

vonbrand