Pytania otagowane jako dfa

Pytania dotyczące deterministycznych automatów skończonych

1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
1
Wielojęzyczna minimalizacja DFA
Jestem zainteresowany niewielkim uogólnieniem DFA. Jak zwykle mamy ustawiony stan , skończony alfabet , działanie zdefiniowane na przez i stan początkowy ; lecz w zwykłym zestawem terminali wziąć rodziny podzbiorów . Wielojęzyczny DFA jest wtedy krotkąQQQΣΣ\SigmaΣ∗Σ∗\Sigma^*QQQδ:Q×Σ→Qδ:Q×Σ→Q\delta : Q\times\Sigma\rightarrow Qq0q0q_0(Ti)i∈1..n(T.ja)ja∈1 ..n(T_i)_{i\in 1..n}QQQMM.M (Q,Σ,δ,q0,(Ti))(Q,Σ,δ,q0,(T.ja))(Q, \Sigma, \delta, q_0, (T_i)) a jest rozpoznawany przez …
2
Czy niedeterministyczne automaty do chodzenia po drzewie są silniejsze niż te deterministyczne?
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa nie są liniowe, ale raczej podane na jakiejś strukturze drzewa. Aby zapobiec „zagubieniu się” naszych maszyn, zdefiniuj …
2
Liczba minimalnych DFA wielkości co najwyżej ?
Niech będzie alfabetem wielkości i rozważmy minimalne DFA, których rozmiar jest ograniczony co najwyżej . Niech oznacza liczbę różnych takich minimalnych DFA.ΣΣ\Sigma222mmmf(m)f(m)f(m) Czy możemy znaleźć formułę zamkniętą dla ?f(m)f(m)f(m) Biorąc pod uwagę, że dla funkcją przejścia DFA o wielkości co najwyżej jest wykres. Ponieważ stopień węzłów jest ograniczony przez , …
1
Algorytm przecięcia DFA dla szczególnych przypadków
Interesują mnie wydajne algorytmy przecięcia DFA w szczególnych przypadkach. Mianowicie, gdy DFA przecinają się, zachowują określoną strukturę i / lub działają na ograniczonym alfabecie. Czy jest jakieś źródło, w którym mogę znaleźć algorytmy takich przypadków? Aby pytanie nie było zbyt szerokie, szczególnie interesująca jest następująca struktura: wszystkie przecinające się DFA …
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.