Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

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 …
4
Czy znalezienie minimalnego wyrażenia regularnego jest problemem NP-zupełnym?
Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail). Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam dokładnej terminologii, ale uzgodnijmy pewną klasę dozwolonych wyrażeń. Zamiast ręcznie tworzyć …
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?
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
Jaki jest najpotężniejszy parser?
Jako poboczny projekt piszę język przy użyciu Pythona. Zacząłem od użycia klonu Flex / Bison o nazwie Ply, ale zbliżam się do krawędzi tego, co mogę wyrazić za pomocą tego stylu gramatyki, i nie jestem zainteresowany zhakowaniem mojego języka z powodu niedopasowania impedancji z narzędzie. Dlatego nie jestem przeciwny pisaniu …
1
Czy istnieje zwykły język drzewa, w którym średnia wysokość drzewa o rozmiarze nie jest ani ani ?
Definiujemy zwykły język drzewa, tak jak w książce TATA : Jest to zestaw drzew akceptowany przez niedeterministyczny automat skończonego drzewa (rozdział 1) lub, równoważnie, zbiór drzew wygenerowany przez zwykłą gramatykę drzewa (rozdział 2). Oba formalizmy są bardzo podobne do znanych analogów strunowych. Czy istnieje zwykły język drzewa, w którym średnia …
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.