Pytania dotyczące deterministycznych automatów skończonych
Przeglądam teorię obliczeń dla zabawy i to pytanie nęka mnie od dłuższego czasu (zabawne, że nie pomyślałem o tym, gdy nauczyłem się teorii automatu w mojej szkole licencjackiej). Więc „dlaczego” dokładnie badamy deterministyczne i niedeterministyczne automaty skończone (DFA / NFA)? Oto kilka...
Po przestudiowaniu deterministycznych automatów skończonych (DFA) w undergrad poczułem, że są one bardzo dobrze rozumiane. Moje pytanie brzmi, czy jest coś, czego wciąż nie rozumiemy. Nie mam na myśli uogólnień DFA, ale oryginalne niezmodyfikowane DFA, które badamy w studiach licencjackich. To...
Przecięcie dwóch (minimalnych) DFA ze stanami n można obliczyć przy użyciu O (n 2 ) czasu i przestrzeni. Jest to ogólnie optymalne, ponieważ otrzymany (minimalny) DFA może mieć n 2 stanów. Jeśli jednak wynikowy minimalny DFA ma stany z, gdzie z = O (n), czy można go obliczyć w przestrzeni n 2-eps ,...
Biorąc pod uwagę dwa ciągi xiy, chcę zbudować DFA o minimalnym rozmiarze, który akceptuje x i odrzuca y. Jednym ze sposobów na to jest wyszukiwanie siłowe. Wymieniasz DFA zaczynając od najmniejszego. Próbujesz każdego DFA, aż znajdziesz taki, który akceptuje x i odrzuca y. Chcę wiedzieć, czy...
W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być...
Pytanie jest proste i bezpośrednie: w przypadku ustalonego , ile (różnych) języków jest akceptowanych przez DFA o rozmiarze n (tj. N stanów)? Formalnie stwierdzę to:nnnnnnnnn Zdefiniuj DFA jako , gdzie wszystko jest jak zwykle, a δ : Q × Σ → Q jest funkcją (być może częściową). Musimy to...
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane...
Istnieją teoretyczne dowody na to, że naiwna konstrukcja produktu kartezjańskiego na przecięciu DFA jest „najlepsza, co możemy zrobić”. Co z konkatenacją dwóch DFA? Trywialna konstrukcja polega na przekształceniu każdego DFA w NFA, dodaniu przejścia epsilon i określeniu wynikowego NFA. Czy możemy...
Dwadzieścia lat temu zbudowałem pakiet wyrażeń regularnych, który obejmował konwersje wyrażeń regularnych na maszynę skończoną (DFA) i obsługiwał wiele zamkniętych operacji wyrażeń regularnych (gwiazda Kleene, konkatenacja, operacje odwrotne, ustawianie itp.). Nie byłem pewien co do najgorszej...
Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA . Jakie są wyniki, jeśli język jest skończony? Problem ten można rozważyć w dwóch modelach: Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy...
Tło: Biorąc pod uwagę dwa deterministyczne automaty skończone A i B, tworzymy iloczyn C, pozwalając, by stany w C były iloczynem kartezjańskim stanów w A i stanów w B. Następnie wybieramy stany przejściowe, początkowe i końcowe, aby język został zaakceptowany przez C to przecięcie języków dla A i...
Jeden z interesujących otwartych problemów dotyczących DFA wymienionych w Czy są jakieś otwarte problemy dotyczące DFA? jest wielkością DFA wymaganą do oddzielenia dwóch łańcuchów długości nnn . Jestem ciekawy, czy są jakieś wyniki dotyczące zdolności losowego DFA do oddzielania dwóch podanych...
Mam naprawdę duży niedeterministyczny automat skończony i muszę go przekonwertować na DFA. Przez duże rozumiem ponad 40 000 stanów. Do tej pory przeprowadziłem kilka eksperymentów i zaprogramowałem domyślny algorytm, który przeszukuje tabelę (jak opisano tutaj ), ale nawet po optymalizacji jest...
Zainspirowany tym pytaniem ciekawi mnie: Jaka jest najgorsza złożoność sprawdzania, czy dany DFA akceptuje ten sam język jako dane wyrażenie regularne? Czy to jest znane? Można mieć nadzieję, że ten problem występuje w P - że algorytm ma wielomian wielkości
Wszystkie moje podręczniki używają tego samego algorytmu do tworzenia DFA, biorąc pod uwagę regex: Najpierw utwórz NFA, który rozpoznaje język regex, a następnie, używając konstrukcji podzbioru (aka „powerset”), przekonwertuj NFA na równoważny DFA ( opcjonalnie minimalizując DFA). Kiedyś słyszałem...
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...
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...
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...
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,...
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...