Pytania otagowane jako automata

Pytania dotyczące urządzeń matematycznych, które odczytują symbol strumienia wejściowego za pomocą symbolu i używają mapy przejścia stanu do wytworzenia strumienia wyjściowego, być może wykorzystując pamięć dodatkową.

1
Moc obliczeniowa deterministycznych versus niedeterministycznych automatów typu min-heap
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu …
2
Jakie jest pochodzenie λ dla pustego łańcucha?
Zazwyczaj używam symbolu dla pustego łańcucha (pusty wyraz lub łańcuch pusty). Ale wiem, że niektórzy ludzie używają λ zamiast ε .εε\varepsilonλλ\lambdaεε\varepsilon Myślę, że pochodzi od słowa „pusty”. Jednak nie wiem, skąd się bierze λ .εε\varepsilonλλ\lambda W teorii automatów istnieje przejście epsilon na automatach, a także mówi się, że jest to …
4
Automatycznie „zgadnij” - co to oznacza?
Zdaję sobie sprawę z tego, że niedeterministyczne automaty wypychające mogą być ulepszeniem w stosunku do automatów deterministycznych, ponieważ mogą „wybierać” spośród kilku stanów i istnieje kilka języków bezkontekstowych, których nie można zaakceptować przez deterministyczne przepychanie. Nadal nie rozumiem, jak dokładnie „wybierają”. Na przykład w przypadku palindormes każde znalezione źródło mówi …
3
Dlaczego operator gwiazdy Kleene jest również nazywany operatorem „zamykania” Kleene?
Przekonałem się, że jeśli nie rozumiem etymologii kryjącej się za terminem cs / programowanie, zwykle oznacza to, że przeoczyłem lub źle zrozumiałem jakąś ważną koncepcję. Nie rozumiem, dlaczego gwiazda Kleene jest również nazywana zamknięciem Kleene. Czy ma to związek z zamknięciami w programowaniu, funkcją ze związanymi zmiennymi nielokalnymi? ... po …
1
Monadyczna logika drugiego rzędu dla manekinów
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 ludzie (w dokumentach) próbowali mi wyjaśnić związek …
2
Jak słowo „produkcja” stało się synonimem słowa „reguła” w kontekście informatyki?
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 angielskim, ale wiem, że reguła odnosi się …
3
Czy zdefiniowanie przejść na każdym możliwym alfabecie jest obowiązkowe w deterministycznych automatach skończonych?
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ć jakieś przykłady?
3
Dlaczego problem zatrzymania jest rozstrzygalny dla LBA?
Czytałem w Wikipedii i innych tekstach, które Problem zatrzymania jest [...] rozstrzygalny dla automatów z ograniczeniami liniowymi (LBA) [i] deterministycznych maszyn ze skończoną pamięcią. Ale wcześniej napisano, że problem zatrzymania jest problemem nierozstrzygalnym, a zatem TM nie może go rozwiązać! Ponieważ LBA są zdefiniowane jako rodzaj bazy TM, czy to …
4
Twierdzenia mostkowe dla teorii grup i języków formalnych
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS (mianowicie za pośrednictwem automatów skończonych ). (Czy ta literatura …
1
Różnica między wyrażeniem regularnym a gramatyką w automatach
Jestem nowy w automatach. Krótkie wprowadzenie do wyrażeń regularnych otrzymałem wczoraj. Przeczytałem różne reguły definiujące wyrażenie regularne. Ale nie jestem w stanie odróżnić wyrażeń regularnych od gramatyki języka (nie uczono mnie gramatyki wyrażeń regularnych). Rozumiem, że gramatyka pomaga nam generować poprawne ciągi w języku, ale wtedy właśnie takie są reguły …
3
Jak utworzyć DFA z wyrażenia regularnego bez użycia NFA?
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 chciałem cię zapytać. Opcja „Regular exp> NFA> Konwersja …
2
Maszyny Turinga z pojedynczą taśmą z wejściem chronionym przed zapisem rozpoznają tylko zwykłe języki
Oto problem: Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki. Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA. Używanie tej TM do symulacji DFA jest bardzo proste. Jednak gdy chcę użyć tego 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.