Pytania otagowane jako automata-theory

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

4
Przecięcie DFA w przestrzeni subkwadratowej?
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 …
1
Decydowanie o pustce przecięcia zwykłych języków w czasie subkwadratowym
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 coś bardziej wydajnego.M 1 , M 2L.1∩ …
1
Języki rozpoznawane przez DFA wielkości wielomianowej
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ć rozpoznawane przez rodziny automatów wielkości, które rosną tylko wielomianowo wraz z długością słowa. …
2
Testowanie, czy litery można zaplanować, aby uzyskać słowo w zwykłym języku
I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne dwie litery nie …
4
Dowód lematu pompowania dla języków bezkontekstowych za pomocą automatów pushdown
Lemat o pompowaniu dla języków regularnych może być udowodnione przez rozważa automat skończony, który rozpoznaje stan języka badanego, zbierając ciąg o długości większej niż jego liczby stanów i stosując zasadę zaszufladkować. Jednak pompowanie lematu dla języków bezkontekstowych (a także lematu Ogdena, który jest nieco bardziej ogólny), zostało udowodnione poprzez rozważenie …
3
Jeśli abstrakcyjna maszyna może się symulować, czy to czyni Turinga kompletnym?
Na przykład w językach programowania często pisze się kompilator / interpreter X-w-X, ale na bardziej ogólnym poziomie wiele znanych systemów Turing-complete może symulować się w imponujący sposób (np. Symulując grę życia Conwaya w grze życia Conwaya ). Moje pytanie brzmi zatem: czy system jest w stanie samodzielnie przeprowadzić symulację, aby …
5
Specjalna klasa języków: języki „okrężne”. Czy to jest znane
Zdefiniuj następującą klasę języków „okrągłych” nad skończonym alfabetem Sigma. W rzeczywistości nazwa już istnieje, aby oznaczać inną rzecz, która się wydaje, stosowana w dziedzinie przetwarzania DNA. AFAICT, to inna klasa języków. Język L jest okrągła wtw dla wszystkich słów w , mamy:wwwΣ∗Σ∗\Sigma^* www należy do L wtedy i tylko wtedy, …
1
Przypuszczenie o dwóch automatach liczników
Chciałbym udowodnić (lub obalić) następującą hipotezę: Przypuszczenie : automaty z dwoma licznikami (2CA) nie mogą zdecydować o następującym języku: n }L={n∣L={n∣L = \{ n \mid trójskładnikowej i binarnej reprezentacji ma zarówno parzystą, jak i nieparzystą długośćnnn}}\} 2CA może łatwo sprawdzić, czy reprezentacja binarna ma parzystą, czy nieparzystą długość (po prostu …
3
Czy koncepcja maszyny Turinga pochodzi od automatów?
Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”? Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down. Zakładam, że Maszyna Turinga pochodzi od automatów, jednak nie …
4
Gdzie większość implementacji REGEX przypada na skalę złożoności?
Większość współczesnych implementacji wyrażeń regularnych, takich jak Perl lub .NET, wykracza poza klasyczną informatyczną definicję REGEX z funkcjami takimi jak lookahead i lookbehind. Czy te funkcje umożliwiają analizowanie instrukcji, których nie można opisać za pomocą skończonego automatu bez odpychania? Jak bardzo zbliża się do ukończenia Turinga, jeśli to możliwe?
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.