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
Jak napisać dowód przy użyciu indukcji na długości ciągu wejściowego?
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ś krok po kroku robił taki dowód. Oto przykładowy problem (ćwiczenie 2.2.10 …
3
Jak udowodnić, że DFA z NFA mogą mieć wykładniczą liczbę stanów?
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 się wskazywać, że liczba stanów DFA mogłaby się wykładniczo skalować pod względem liczby …
3
Czy ten język jest zdefiniowany przy użyciu podwójnych liczb pierwszych regularnych?
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 . Mój problem polega na …
4
Jak pokazać, że „odwrócony” język regularny jest regularny
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 słów z odwrócone. ”LLLLRLRL^{R}LRLRL^{R}LLL
2
Czy mogą istnieć „martwe stany” w gramatyce bezkontekstowej?
Czy gramatyka bezkontekstowa może zawierać „martwe stany” z automatu, np G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? B→CB→CB\to CC→cCC→cCC\to cC will loop forever and never generate a word. Is this allowed or MUST production rules end with an terminal at …
4
Zdefiniowanie problemu zatrzymania dla niedeterministycznych automatów
Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna. Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych rodzajów automatów. Zauważyłem również, że determinizm jest często mniej lub bardziej dorozumiany w …
2
Języki akceptowane przez zmodyfikowane wersje automatów skończonych
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 δ:Q×Σ→Qδ:Q×Σ→Q\delta : Q \times \Sigma \rightarrow Q powinna być …
1
Potwierdzenie zamknięcia w zamian języków akceptowanych przez automaty 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 języki są rozpoznawane przez maszyny z jednym licznikiem?
Maszyny liczące z dwoma lub więcej licznikami są zwykle pokazywane jako równoważne maszynom Turinga w kursach teorii teorii obliczeń. Jednak nie widziałem formalnej analizy tego, które języki mogą być rozpoznawane przez maszynę z jednym kontem. Czy te języki są równoważne z językami bezkontekstowymi (być może przez jakąś sprytną konstrukcję odnoszącą …
5
Czy istnieją nierozstrzygalne właściwości niekompletnych automatów?
Czy istnieją nierozstrzygalne właściwości automatów z ograniczeniami liniowymi (unikanie sztuczki z pustym językiem ustawiania)? A co z deterministycznym automatem skończonym? (odłóż na bok trudność). Chciałbym uzyskać przykład (jeśli to możliwe) niezdecydowanego problemu, który jest zdefiniowany bez jawnego używania maszyn Turinga . Czy kompletność modelu Turinga jest niezbędna do obsługi problemów …
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.