Biorąc pod uwagę alfabet Σ = { a , b }Σ={za,b}\Sigma = \{ a,b \} , ile jest różnych języków regularnych, które może zaakceptować nnn stanowy niedeterministyczny automat skończony? Jako przykład rozważmy n=3n=3n=3 . Następnie mamy 2182182^{18} różnych konfiguracji przejścia i 23232^3 różne...
Chcę wiedzieć, czy można rozwiązać następujący problem: Instancja: NFA A z n stanami Pytanie: Czy istnieje jakaś liczba pierwsza p, taka, że A akceptuje pewien ciąg długości p. Wierzę, że ten problem jest nierozstrzygalny, ale nie mogę tego udowodnić. Decydent może łatwo mieć algorytm, aby...
Jestem programistą z automatami, ale nie logiką. Przeczytałem w artykułach, że te dwa są ze sobą ściśle powiązane. Deterministyczne automaty skończone (DFA), automaty drzewa i automaty z widocznym przesunięciem w dół są powiązane z logiką Monadic drugiego rzędu (MSO). Chociaż rozumiem automaty i...
Wiem, że możemy zminimalizować DFA poprzez znajdowanie i łączenie równoważnych stanów, ale dlaczego nie możemy zrobić tego samego z NFA? Nie szukam dowodu ani nic takiego - chyba że dowód jest łatwiejszy do zrozumienia. Chcę tylko intuicyjnie zrozumieć, dlaczego minimalizacja NFA jest tak trudna,...
Studiuję języki formalne i systemy baz produkcyjnych (systemy baz reguł) i jestem trochę zdezorientowany, dlaczego te dwa słowa „produkcja” i „reguła” oznaczają to samo w tak wielu kontekstach w informatyce. W języku angielskim nie wydają się oznaczać tego samego. Nie jestem rodzimym językiem...
Jutro jest moja prezentacja i chcę wyjaśnić moje koncepcje… Przeczytałem to w DFA: „Dla każdego stanu należy zdefiniować przejście na wszystkie możliwe symbole (alfabet)”. Czy dla każdego stanu zdefiniowanie przejścia na wszystkie możliwe symbole jest obowiązkowe w DFA? Jeśli nie, proszę podać...
Właśnie zacząłem czytać o teorii obliczeń. Jeśli porównamy, który ma większą moc (w przyjmowaniu ciągów), oba są takie same. Ale co z wydajnością? DFA będzie szybki w porównaniu do NFA, ponieważ ma tylko jedną przewagę wychodzącą i nie będzie dwuznaczności. Ale w przypadku NFA musimy sprawdzić...
Zastanawiam się, jaka jest złożoność czasowa określania pustki dla dwukierunkowych DFA? Oznacza to, że skończone automaty mogą przesuwać się wstecz na swojej taśmie wejściowej tylko do odczytu. Według Wikipedii są one równoważne DFA, chociaż równoważny DFA może być wykładniczo większy. Znalazłem...
Jeśli nie, to co to znaczy, że dla jakiegoś stanu qqq i jakiegoś symbolu zaaa , δ( q, a )δ(q,a)\delta(q, a) nie
Na poniższym zdjęciu próbuję dowiedzieć się, co dokładnie akceptuje ten NFA. To, co mnie dezorientuje, to skok przy q 0 .ϵϵ\epsilonq0q0q_0 Jeśli zostanie wprowadzone , czy system przejdzie zarówno do q 0, jak i do q 1 (stan akceptacji)?000q0q0q_0 q1q1q_1 Jeśli wprowadzona zostanie , czy...
Celem jest utworzenie DFA z wyrażenia regularnego, a użycie opcji „Regular exp> NFA> Konwersja DFA” nie jest opcją. Jak należy to zrobić? Zadałem to pytanie naszemu profesorowi, ale powiedział mi, że możemy korzystać z intuicji i uprzejmie odmówił podania jakichkolwiek wyjaśnień. Więc...
Czy biorąc pod uwagę dwa DFA, problem ze znalezieniem, czy generują ten sam język, stanowi problem rozstrzygalny? Wiem już, że równość dwóch CFL nie jest rozstrzygalna ale co z równością dwóch DFA? biorąc pod uwagę, że większość problemów związanych z DFA jest rozstrzygalna, czy to również jest...
To może być głupie pytanie. Wydaje się jasne, że FSA, ponieważ jest skończona, może zliczyć tylko liczbę symboli w ciągu wejściowym do liczby ograniczonej liczbą stanów. Ale teraz załóżmy, że wyposażamy FSA w funkcje wyjściowe (np. Drukowanie). Byłoby wówczas bardzo łatwo zbudować maszynę zdolną do...
Mam prosty problem z utworzeniem DFA, który akceptuje wszystkie dane wejściowe zaczynające się od podwójnych liter (aa, bb) lub kończące się na podwójnych literach (aa, bb), biorąc pod uwagę, że jest zestawem alfabetu dany język.Σ={a,b}Σ={a,b}\Sigma =\{a, b\} Próbowałem rozwiązać to w sposób...
Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem Σ , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) M taki, że A ⊆ L ( M ) i L ( M ) ⊆ Σ ∗ ∖ BA,BA,BA,BΣΣ\SigmaMMMA⊆L(M)A⊆L(M)A \subseteq L(M)L(M)⊆Σ∗∖BL(M)⊆Σ∗∖BL(M) \subseteq \Sigma^*\setminus B ? Innymi słowy,...
Miałem wrażenie, że nasze komputery, będąc skończone, ostatecznie nie są potężniejsze niż (wyjątkowo duże) skończone maszyny stanowe. Jednak maszyny Turinga liniowo ograniczone są również skończone, ale wydaje się, że zwykłe języki są ściśle niewłaściwym podzbiorem języków wrażliwych na...
Minimalizowanie deterministycznych automatów skończonych (DFA) to problem, który został dokładnie przestudiowany w literaturze, i zaproponowano kilka algorytmów w celu rozwiązania następującego problemu: Biorąc pod uwagę DFA , oblicz odpowiednią minimalną DFA akceptującą ten sam język, co \ mathscr...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Jeśli dobrze rozumiem, NFA mają taką samą moc ekspresji jak wyrażenia regularne. Często odczytywanie równoważnych wyrażeń regularnych z NFA jest łatwe: przekładasz cykle na gwiazdy, skrzyżowania jako alternatywy i tak dalej. Ale co zrobić w tym przypadku: [ źródło ] Nakładające się cykle...
Algorytm Brzozowskiego można rozszerzyć na automaty Moore'a, ale jego złożoność czasowa jest generalnie wykładnicza. Czy istnieje jakiś inny algorytm minimalizacji automatów Moore? Jakie są czasy działania tych algorytmów, jeśli takie