Pytania otagowane jako finite-automata

Pytania dotyczące automatów skończonych, elementarnego modelu automatów ze skończoną pamięcią. Jest to odpowiednik zwykłych języków i podstawa dla wielu bardziej złożonych modeli.


2
Optymalny solver krótkowzrocznego labiryntu
Wygłupiałem się z prezentacją Google Blocky's Maze i przypomniałem sobie starą zasadę, że jeśli chcesz rozwiązać labirynt, trzymaj lewą rękę przy ścianie. Działa to dla każdego prostego połączenia labiryntu i może być zrealizowane przez skończony przetwornik. Niech nasz robot będzie reprezentowany przez przetwornik z następującymi czynnościami i obserwowalnymi: Czynności: idź …


4
NFA z wykładniczą liczbą stanów po rozpoznaniu
Jak zbudować przykład DFA, który ma stanów, w których równoważny NFA ma n stanów. Oczywiście zestaw stanów DFA powinien zawierać wszystkie podzestawy zestawu stanów NFA, ale nie wiem jak zacząć. Jakieś sugestie, żeby postawić mnie na właściwej drodze?2n2n2^nnnn


3
Warunek nieskończoności języka automatu skończonego
Istnieje twierdzenie, które mówi, że: Biorąc pod uwagę automat skończony mający stanów, jeśli istnieje ciąg którego długość spełnia wówczas język akceptowany przez automat jest nieskończony.nnnwwwn ≤ | w | ≤ 2 n - 1n≤|w|≤2n−1n \leq |w| \leq 2n-1 Rozumiem ograniczenie , ale nie rozumiem, dlaczego ograniczenie jest tam.| w | …

4
Dlaczego powinniśmy studiować wszystkie trzy formy reprezentacji automatów skończonych?
DFA, NFA i epsilon NFA wszystkie trzy pozwalają nam reprezentować konkretny język. Za pomocą dowolnej z tych reprezentacji możemy dojść do tego samego wyrażenia regularnego, dlaczego więc musimy studiować wszystkie trzy formy reprezentacji automatów skończonych? Można wyjaśnić, co NFA może zrobić, czego DFA nie może zrobić, to znaczy, że NFA …

3
DFA za akceptację wszystkich ciągów binarnych mocy formy
Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .nnn Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób: Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób: Możemy zastosować dobrze zdefiniowaną procedurę, aby utworzyć tego rodzaju DFA. Czy jednak może istnieć …

1
Czy niedeterminizm w niedeterministycznej maszynie Turinga różni się od automatów skończonych i automatów wypychających?
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 istnienie w sss, jeśli istnieje przejście tego …


4
Jaki jest dobry algorytm do generowania losowych DFA?
Generuję losowe DFA, aby przetestować na nich algorytm redukcji DFA. Algorytm, którego teraz używam, jest następujący: dla każdego stanu , dla każdego symbolu w alfabecie dodaj do jakiegoś losowego stanu. Każde państwo ma takie samo prawdopodobieństwo, że stanie się stanem końcowym.qqqdodocδ( q, c )δ(q,do)\delta (q, c) Czy to dobra metoda …

1
Różnica między językami akceptowanymi przez dwa DFA o różnych stanach początkowych / stanach akceptacji?
Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany końcowe (akceptujące) mogą …


4
Słowa, które mają ten sam prawy i lewy skojarzony produkt
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 do lewej, mnożąc zgodnie z poniższą tabelą: ×zabdozazadobbzazadododobza×abcaaacbcabcbca\qquad \displaystyle\begin{array}{c|ccc} \times …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.