Pytania dotyczące automatów, gramatyk formalnych lub innych modeli obliczeniowych, które szczególnie odnoszą się do użycia niedeterminizmu. Nie mylić z przypadkowością lub niejednoznacznością!
Rozmawiałem o tym, jak zdefiniować kwantowe maszyny Turinga? i czuję, że kwantowa TM i niedetermistyczna TM są jednym i tym samym. Odpowiedzi na inne pytanie nie dotyczą tego. Czy te dwa modele są takie same? Jeśli nie, Jakie są różnice między Quantum TM i NDTM? Czy jest jakieś obliczenie,...
Jakie różnice i zależności występują między algorytmami losowymi a algorytmami niedeterministycznymi? Z Wikipedii Randomizowane algorytm jest algorytmem, w którym stosuje się stopniem losowości jako część logiki. Algorytm zwykle wykorzystuje jednolicie losowe bity jako pomocnicze dane wejściowe...
Wiemy, że DFA są równoważne NFA pod względem siły wyrazu; znany jest również algorytm konwersji NFA na DFA (niestety teraz znam twórcę tego algorytmu), który w najgorszym przypadku daje nam 2S2S2^S stany S , jeśli nasz NFA ma stany SSS Moje pytanie brzmi: co determinuje najgorszy...
Automat jest abstrakcyjnym modelem komputera cyfrowego. Komputery cyfrowe są całkowicie deterministyczne; ich stan w dowolnym momencie jest wyjątkowo przewidywalny na podstawie stanu wejściowego i początkowego. Kiedy próbujemy modelować prawdziwe systemy, dlaczego włączamy niedeterminizm do teorii...
Wszystkie niedeterministyczne skończone automaty można przekształcić w równoważne deterministyczne skończone automaty. Jednak deterministyczne automaty skończone zezwalają tylko na jedną strzałkę na symbol wskazującą na stan. Dlatego jego stany powinny należeć do zestawu sił stanów NFA. To wydaje...
Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna. Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych...
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie...
Zdaję sobie sprawę z tego, że niedeterministyczne automaty wypychające mogą być ulepszeniem w stosunku do automatów deterministycznych, ponieważ mogą „wybierać” spośród kilku stanów i istnieje kilka języków bezkontekstowych, których nie można zaakceptować przez deterministyczne przepychanie. Nadal...
Mam na myśli to [zabawne] pytanie. Dlaczego niedeterministyczny automat skończony nazywa się niedeterministyczny, podczas gdy my definiujemy przejścia dla danych wejściowych. Cóż, mimo że istnieje wiele przejść i epsilon , są one zdefiniowane, co oznacza, że maszyna jest deterministyczna dla tych...
Wiem, że możemy zminimalizować DFA poprzez znajdowanie i łączenie równoważnych stanów, ale dlaczego nie możemy zrobić tego samego z NFA? Nie szukam dowodu ani nic takiego - chyba że dowód jest łatwiejszy do zrozumienia. Chcę tylko intuicyjnie zrozumieć, dlaczego minimalizacja NFA jest tak trudna,...
Z Wikipedii na temat algorytmów losowych Należy rozróżnić algorytmy, które wykorzystują losowe dane wejściowe w celu zmniejszenia oczekiwanego czasu działania lub zużycia pamięci, ale zawsze kończą się poprawnym wynikiem w ograniczonym czasie, a algorytmy probabilistyczne , które w zależności...
Właśnie zacząłem czytać o teorii obliczeń. Jeśli porównamy, który ma większą moc (w przyjmowaniu ciągów), oba są takie same. Ale co z wydajnością? DFA będzie szybki w porównaniu do NFA, ponieważ ma tylko jedną przewagę wychodzącą i nie będzie dwuznaczności. Ale w przypadku NFA musimy sprawdzić...
Jutro jest moja prezentacja i chcę wyjaśnić moje koncepcje… Przeczytałem to w DFA: „Dla każdego stanu należy zdefiniować przejście na wszystkie możliwe symbole (alfabet)”. Czy dla każdego stanu zdefiniowanie przejścia na wszystkie możliwe symbole jest obowiązkowe w DFA? Jeśli nie, proszę podać...
Na poniższym zdjęciu próbuję dowiedzieć się, co dokładnie akceptuje ten NFA. To, co mnie dezorientuje, to skok przy q 0 .ϵϵ\epsilonq0q0q_0 Jeśli zostanie wprowadzone , czy system przejdzie zarówno do q 0, jak i do q 1 (stan akceptacji)?000q0q0q_0 q1q1q_1 Jeśli wprowadzona zostanie , czy...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
My podręcznik mówi „określamy funkcji następująco: i . Zauważ, że biorąc pod uwagę , możemy łatwo znaleźć w czasie liczbę taką, że jest umieszczone pomiędzy i . "f:N→Nf:N→Nf\colon
Uczę się, jak konwertować NFA na DFA i chcę się upewnić, że robię to dobrze. Oczywiście powrót w innym kierunku nie jest niczym. Czy ktoś zna algorytm sprawdzający, czy DFA jest równoważne z
Niech łańcuch wejściowy będzie podany jako w1w2...wnw1w2...wnw_1w_2...w_n. Następnie, jeśli NFA jest obecnie w stanierrr (i przeczytał wejście do alfabetu wiwiw_i ), a następnie przed odczytaniem następnego symbolu wejściowego NFA dzieli się na dwa NFA, z których jeden jest w stanie rrr i inne...
Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący: Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej...
Pracuję nad Sipser Book (wydanie drugie) i natknąłem się na ten przykład, którego nie rozumiem. W książce stwierdzono, że ten NFA akceptuje pusty ciąg .ϵϵ\epsilon Czy ktoś mógłby mnie przekonać, dlaczego tak jest? Rozumiem, że przejdzie do co nie jest stanem