Pytania otagowane jako automata-theory

Teoria automatów, w tym maszyny abstrakcyjne, gramatyki, parsowanie, wnioskowanie gramatyczne, przetworniki i techniki skończone

11
Jakie oświecenie powinienem osiągnąć po przestudiowaniu 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 odpowiedzi, które wymyśliłem po monologowaniu, ale wciąż nie …
5
Czy hierarchia Chomsky'ego jest przestarzała?
Hierarchia Chomsky'ego (–Schützenberger) jest używana w podręcznikach teoretycznej informatyki, ale oczywiście obejmuje tylko bardzo niewielką część języków formalnych (REG, CFL, CSL, RE) w porównaniu z pełnym diagramem złożoności Zoo . Czy hierarchia odgrywa już jakąkolwiek rolę w bieżących badaniach? Znalazłem niewiele odniesień do Chomsky'ego tutaj na cstheory.stackexchange, aw Zoo Złożoności …
10
Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?
Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?
9
Jaka jest różnica między niedeterminizmem a przypadkowością?
Niedawno to usłyszałem - „Maszyna niedeterministyczna to nie to samo, co maszyna probabilistyczna. Mówiąc prymitywnie, maszyna niedeterministyczna to maszyna probabilistyczna, w której prawdopodobieństwa przejścia nie są znane”. Czuję, że rozumiem, ale tak naprawdę nie. Czy ktoś mógłby mi to wyjaśnić (w kontekście maszyn lub ogólnie)? Edycja 1: Aby wyjaśnić, cytat …
14
Jak praktyczna jest teoria automatów?
Zawsze istnieje sposób na zastosowanie w tematach związanych z informatyką teoretyczną. Jednak podręczniki i kursy licencjackie zwykle nie wyjaśniają, dlaczego teoria automatów jest ważnym tematem i czy nadal ma zastosowania w praktyce. Dlatego studenci mogą mieć problemy ze zrozumieniem znaczenia teorii automatów i mogą myśleć, że nie ma ona już …
6
Wyrażenia regularne nie są
Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego. Na przykład „wyrażenie regularne” /^1?$|^(11+?)\1+$/ stworzona przez znaną osobowość Perla Abigail (i część zestawu testów Perla od 2002 r.) opisuje maszynę, która akceptuje tylko złożone liczby …
1
Racjonalna hierarchia nieracjonalnych automatów i języków Eilenberga - gdzie jest teraz?
W przedmowie do swoich bardzo wpływowych książek Automata, języki i maszyny (tomy A, B) Samuel Eilenberg kusząco obiecał tomy C i D dotyczące „hierarchii (zwanej racjonalną hierarchią) nieracjonalnych zjawisk… przy użyciu relacji racjonalnych jako narzędzie do porównywania. Racjonalne zestawy znajdują się na dole tej hierarchii. W górę napotyka się zjawiska …
2
Czy { } nie jest kontekstowe?
Czy język { } jest bezkontekstowy?zajabjotdok | i≠j,i≠k,j≠k aibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Uświadomiłem sobie, że spotkałem prawie wszystkie warianty tego pytania z różnymi warunkami dotyczącymi związku między i, j i k, ale nie tym. Domyślam się, że nie jest pozbawiony kontekstu, …
4
Czy istnieją „małe” maszyny, które mogą skutecznie dopasowywać wyrażenia regularne?
Dobrze wiadomo, że wyrażenie regularne może zostać rozpoznane przez niedeterministyczny automat skończony o wielkości proporcjonalnej do wyrażenia regularnego lub przez deterministyczny FA, ​​który jest potencjalnie większy wykładniczo. Ponadto, biorąc pod uwagę ciąg i wyrażenie regularne , NFA może przetestować członkostwo w czasie proporcjonalnym do | s | \ cdot | …
2
Warunki dla uniwersalności NFA
Rozważ niedeterministyczny automat skończony A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F)A = (Q, \Sigma, \delta, q_0, F) i funkcję f(n)f(n)f(n) . Dodatkowo definiujemy Σ≤k=⋃i≤kΣiΣ≤k=⋃i≤kΣi\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i . Teraz przeanalizujmy następujące oświadczenie: Jeżeli Σ≤f(|Q|)⊆L(A)Σ≤f(|Q|)⊆L(A)\Sigma^{\leq f(|Q|)} \subseteq L(A) , to L(A)=Σ∗L(A)=Σ∗L(A) = \Sigma^* . Łatwo jest wykazać, że dla f(n)=2n+1f(n)=2n+1f(n) = 2^n+1 jest to …
4
Czy istnieje niepełny model Turinga, którego problem zatrzymania jest nierozstrzygalny?
Nie mogę wymyślić żadnego takiego modelu, może jakiejś formy wypisanego rachunku lambda? jakiś elementarny automat komórkowy? To prawie obaliłoby „zasadę równoważności obliczeniowej” Wolframa: Prawie wszystkie procesy, które nie są oczywiście proste, można postrzegać jako obliczenia o podobnym stopniu zaawansowania
2
Gramatyka i typy wrażliwe na kontekst
1) Jaki, jeśli w ogóle, jest związek między pisaniem statycznym a gramatyką formalną? 2) Czy w szczególności byłoby możliwe, aby automat z ograniczeniem liniowym sprawdził, czy, powiedzmy, program C ++ lub SML był dobrze napisany? Automat zagnieżdżonego stosu? 3) Czy istnieje naturalny sposób na wyrażenie zasad pisania statycznego w formalnych …
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.