Pytania dotyczące automatów skończonych, elementarnego modelu automatów ze skończoną pamięcią. Jest to odpowiednik zwykłych języków i podstawa dla wielu bardziej złożonych modeli.
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w...
W teorii automatów wszyscy od samego początku czytamy automaty jako automaty skończone. Chcę wiedzieć, dlaczego automaty są skończone? Dla jasności, co to jest w skończonym automacie - alfabet, język, ciągi znaków wyrażeń regularnych, czy co? Czy istnieją (teoretycznie) jakieś nieskończone...
W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę K_5 , kompletny wykres na pięciu węzłach . Yuval pokazał...
Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych. Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
Robię prezentację na temat maszyn Turinga i chciałem przedstawić trochę informacji na temat FSM przed wprowadzeniem maszyn Turinga. Problem w tym, że tak naprawdę nie wiem, co BARDZO różni się od siebie. Oto, co wiem, że jest inaczej: FSM ma sekwencyjne stany w zależności od spełnienia...
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo...
Wiemy, że DFA są równoważne NFA pod względem siły wyrazu; znany jest również algorytm konwersji NFA na DFA (niestety teraz znam twórcę tego algorytmu), który w najgorszym przypadku daje nam 2S2S2^S stany S , jeśli nasz NFA ma stany SSS Moje pytanie brzmi: co determinuje najgorszy...
Wszystkie niedeterministyczne skończone automaty można przekształcić w równoważne deterministyczne skończone automaty. Jednak deterministyczne automaty skończone zezwalają tylko na jedną strzałkę na symbol wskazującą na stan. Dlatego jego stany powinny należeć do zestawu sił stanów NFA. To wydaje...
W moim kursie teorii obliczeń wiele naszych problemów wiąże się z wykorzystaniem indukcji na długości łańcucha wejściowego do udowodnienia twierdzeń o automatach skończonych. Rozumiem indukcję matematyczną, ale kiedy pojawiają się struny, naprawdę się potykam. Byłbym bardzo wdzięczny, gdyby ktoś...
Pozwolić L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Czy regularny?LLL To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych ....
Utknąłem na następujące pytanie: „Zwykłe języki są dokładnie tymi, które są akceptowane przez automaty skończone. Biorąc pod uwagę ten fakt, pokaż, że jeśli język jest akceptowany przez jakiś automat skończony, wówczas jest również akceptowany przez niektóre skończone; składa się ze wszystkich...
Na przykład, gdy weźmiemy pod uwagę DFA, który zezwala na łańcuchy bez podłańcuchów 00lub 11mogę wygenerować następujące dwa
Użyłem FSM w projektach cyfrowych układów sekwencyjnych. Ale nie znam Finata Automata. Czy ktoś może mi pomóc w zrozumieniu „podstawowej” różnicy między nimi?
Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:GGG odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,GGGN′N′N' używając konstrukcji powerset, aby uzyskać...
Mówi się, że przecięcie języka L bez kontekstu z językiem zwykłym M jest zawsze wolne od kontekstu. Zrozumiałem dowód na konstrukcję wielu produktów, ale wciąż nie rozumiem, dlaczego nie zawiera kontekstu, ale nie jest regularny. Język generowany przez takie skrzyżowanie ma ciągi znaków, które są...
Deterministyczny automat skończony (DFA) to model maszyny stanów zdolny do przyjmowania wszystkich i tylko zwykłych języków. DFA można (i zwykle są) definiować w taki sposób, że każdy stan musi zapewnić pewne przejście dla wszystkich elementów alfabetu wejściowego; innymi słowy, funkcja przejścia...
Biorąc pod uwagę język , zdefiniuj zestaw długości jako zestaw długości słów w : LLLLLLLLLLS(L)={|u|∣u∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Które zestawy liczb całkowitych mogą być zestawem długości zwykłego
Ostatnio zadano interesujące pytanie, a następnie usunięto. W przypadku zwykłego języka jego złożoność DFA jest wielkością minimalnej akceptacji DFA, a złożoność NFA jest wielkością minimalnej akceptacji NFA. Dobrze wiadomo, że istnieje wykładnicza separacja między tymi dwoma złożonościami,...
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...