Pytania otagowane jako automata

Pytania dotyczące urządzeń matematycznych, które odczytują symbol strumienia wejściowego za pomocą symbolu i używają mapy przejścia stanu do wytworzenia strumienia wyjściowego, być może wykorzystując pamięć dodatkową.

1
Algorytm do tłumaczenia deterministycznego automatu Büchi na LTL (jeśli to możliwe)
Logika LTL i deterministycznych automatów BUCHI są nieporównywalne: DBA nie może wyrazić , i nie mogą wyrażać LTL „co najmniej dziwne jest każda litera«a»” . Ale czasami interesujące jest, czy język DBA może być wyrażony w LTL.FGaFGaFGa Potrzebuję algorytmu, który decyduje, czy język danego DBA można opisać w LTL. Czy …
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ć …
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.