Pytania oznaczone «automata-theory»

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...

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...

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...

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...

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...

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ęść...

Potrzebuję skończonej książki z teorią automatów z wieloma przykładami, które mogę wykorzystać do samodzielnej nauki i przygotowania się do

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...

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...

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...

Zastanawiałem się, czy istnieje `` lepszy '' (wyjaśnię, w jakim sensie) algorytm rozpoczynający się od DFA i konstruujący wyrażenie regularne r takie, że L ( A ) = L ( r ) , niż ten w książka Hopcroft i Ullman (1979). Tam, zbiory R k i j są używane do reprezentowania komplety strun, które odbywają...

Napraw liczbę całkowitą i alfabet Σ = { 0 , 1 } . Zdefiniuj D F A ( n ) jako zbiór wszystkich automatów skończonych w stanach n ze stanem początkowym 1. Rozważamy wszystkie DFA (nie tylko połączone, minimalne lub nie-zdegenerowane); w ten sposób | D F A ( n ) | = n 2 n 2 n...

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...

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...

Przecięcie dwóch (minimalnych) DFA ze stanami n można obliczyć przy użyciu O (n 2 ) czasu i przestrzeni. Jest to ogólnie optymalne, ponieważ otrzymany (minimalny) DFA może mieć n 2 stanów. Jeśli jednak wynikowy minimalny DFA ma stany z, gdzie z = O (n), czy można go obliczyć w przestrzeni n 2-eps ,...

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...

Dla dowolnego języka ponad zdefiniuj Słowami, składa się ze wszystkich dla których istnieje o równej długości, tak że .Σ * l 1 / 2 = { x ∈ Σ * : x y ∈ L , Y ∈ Σ | x | } . L 1 / 2 x Y x Y ∈ LL.LLΣ∗Σ∗\Sigma^*L.1 / 2= { x ∈ Σ∗: x y∈ L. , y∈ Σ| x |} .L1/2={x∈Σ∗:xy∈L,y∈Σ|x|}.L_{1/2} = \{x \in \Sigma^*...

Biorąc pod uwagę dwa ciągi xiy, chcę zbudować DFA o minimalnym rozmiarze, który akceptuje x i odrzuca y. Jednym ze sposobów na to jest wyszukiwanie siłowe. Wymieniasz DFA zaczynając od najmniejszego. Próbujesz każdego DFA, aż znajdziesz taki, który akceptuje x i odrzuca y. Chcę wiedzieć, czy...

Niech będą dwoma zwykłymi językami podanymi przez NFA M_1 jako dane wejściowe.M 1 , M 2L.1, L2)L1,L2L_1,L_2M.1, M2)M1,M2M_1,M_2 Załóżmy, że chcielibyśmy sprawdzić, czy . Można to wyraźnie zrobić za pomocą algorytmu kwadratowego, który oblicza automat produktu , , ale zastanawiałem się, czy wiadomo...

W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być...