Pytania otagowane jako automata-theory

Teoria automatów, w tym maszyny abstrakcyjne, gramatyki, parsowanie, wnioskowanie gramatyczne, przetworniki i techniki skończone

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 …
3
Trudność ze znalezieniem co najwyżej słowa
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?
1
Uogólnienie stwierdzenia, że ​​monoid rozpoznaje język iff monoid syntaktyczny dzieli monoid
Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to ML=φ−1(φ(L)))L=φ−1(φ(L)))L = \varphi^{-1}(\varphi(L))) Mamy więc ładny wynik: Monoid rozpoznaje jeśli jest homomorficznym obrazem submonoidu (napisanego jako …
1
Przejście do członkostwa monoidów w DFA
Biorąc pod uwagę pełne DFA A=(Q,Γ,δ,F)A=(Q,Γ,δ,F)A=(Q, \Gamma, \delta, F), możemy zdefiniować zbiór funkcji fafaf_a dla każdego a∈Γa∈Γa\in \Gammai z fa:Q→Qfa:Q→Qf_a:Q\rightarrow Q, fa(q)=δ(q,a)fa(q)=δ(q,a)f_a(q)=\delta(q, a). Możemy uogólnić to pojęcie na słowow=a1,⋯,amw=a1,⋯,amw=a_1, \cdots, a_m i fw=fa1∘⋯∘famfw=fa1∘⋯∘famf_w=f_{a_1}\circ \cdots \circ f_{a_m} gdzie ∘∘\circoznacza skład funkcji. Ponadto oznaczamyG={fw∣w∈Γ∗}G={fw∣w∈Γ∗}G=\{f_w\mid w\in \Gamma^*\} i GGG jest monoidem. [GGGjest zwykle …
1
Rozpoznawanie automatów
Pozwolić ΣΣ\Sigmabyć skończonym alfabetem. kod XXX nad ΣΣ\Sigma jest podzbiorem Σ∗Σ∗\Sigma^* tak, że każde słowo w X∗X∗X^* może być jednoznacznie przedstawiony jako połączenie słów w XXX. KodXXXjest skończony, jeśli| X||X||X|jest skończony. Co wiadomo na temat (minimalnego) rozpoznawania automatówX∗X∗X^*dla skończonego kodu ? Czy istnieje jakaś charakterystyka takich automatów (pod względem budowy …
3
Klasa języków rozpoznawalna przez 3-stanowe TM z pojedynczą taśmą
Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym q0q0q_0, stan akceptacji i stan odrzucenia ). Zauważ, że zezwalam na dowolne (skończone) alfabety taśmowe (tzn. Alfabet na taśmie nie jest ograniczony do równego alfabetowi wejściowemu).qacceptqacceptq_{accept}qrejectqrejectq_{reject} Dla wygody zadzwoń do klasy języków …
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
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść …
1
Reżyserowane multigrafie jako minimalne automaty
Biorąc pod uwagę zwykły język L.LL na alfabecie ZAAA, jego minimalny deterministyczny automat może być postrzegany jako ukierunkowana połączona multigraf ze stałym stopniem | A ||A||A|i zaznaczony stan początkowy (poprzez zapomnienie etykiet przejść, stanów końcowych). Zachowujemy stan początkowy, ponieważ każdy wierzchołek musi być z niego dostępny. Czy odwrotność jest prawdziwa? …
2
Uogólnienie algorytmu minimalizacji DFA Brzozowskiego do automatów skończonych z różnymi klasami stanów akceptujących?
Algorytm Brzozowskiego do przekształcania DFA w równoważny DFA stanu minimalnego jest niezwykle prosty: jeśli oznacza NFA utworzony przez odwrócenie wszystkich krawędzi w DFA , czyniąc stary stan początkowy stanem akceptującym i czyniąc starym akceptowaniem stwierdza początek stanów i jeżeli oznacza wynik zastosowania konstrukcji podzbioru do NFA , a następnie jest …
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 …
4
Dlaczego automaty z ograniczeniem liniowym nie są tak popularne jak inne automaty?
Z mojego doświadczenia wynika, że ​​języki kontekstowe i automaty z ograniczeniami liniowymi są często pomijane lub przewijane na kursach teorii obliczeń, a nawet są pomijane w niektórych znaczących podręcznikach, chociaż automaty skończone i zmniejszające są bardzo popularne. Z pewnością musi istnieć dobry powód, dla którego LBA są mniej skoncentrowane niż …
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.