Pytania otagowane jako closure-properties

Pytania o operacje na obiektach, których wynikiem są obiekty tego samego rodzaju.

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
Czy zestawy przed i po dla gramatyk bezkontekstowych zawsze są pozbawione kontekstu?
Niech GGG będzie gramatyką bezkontekstową. Łańcuch zacisków i nieterminali z GGG mówi się zdań tworzą z GGG , czy można go otrzymać stosując produkcje GGG zero lub więcej razy symbolu startu SSS . Niech SF(G)SF⁡(G)\operatorname{SF}(G) będzie zbiorem form zdaniowych GGG . Niech α∈SF(G)α∈SF⁡(G)\alpha \in \operatorname{SF}(G) i pozwolić ββ\beta być podłańcuchem …
7
Czy
Jeśli jest regularne, to czy wynika z tego, że jest regularne? AA2A2A^2AAA Moja próba na dowód: Tak, ponieważ sprzeczność zakłada, że nie jest regularne. Następnie .A 2 = A ⋅ AAAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Ponieważ łączenie dwóch nieregularnych języków nie jest regularne, nie może być regularne. Jest to sprzeczne …
4
Operacje, w których klasa nierozstrzygalnych języków nie jest zamknięta
Czy istnieją nierozstrzygalne języki, tak że ich związek / język przecięcia / konkatenacji jest rozstrzygalny? Jaka jest fizyczna interpretacja takiego przykładu, ponieważ ogólnie nierozstrzygalne języki nie są zamknięte w ramach tych operacji? Co możemy powiedzieć o zamknięciu kleene? Czy mamy też na to przykłady? Czy to znaczy, że zamknięcie nierozstrzygalnego …
1
Wykazać, że dopełnienie
Chcę udowodnić, że dopełnienie nie używa regularnie właściwości zamknięcia.{ 0n1n| N ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} Rozumiem, że można użyć lematu pompującego, aby udowodnić, że nie jest zwykłym językiem. Rozumiem również, że zwykłe języki są zamknięte w ramach operacji uzupełniania. Czy to jednak oznacza również, że uzupełnienie języka nieregularnego …
1
Konstruujesz wszystkie języki bezkontekstowe z zestawu języków podstawowych i właściwości zamknięcia?
Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego języka, języka zawierającego pusty ciąg i języków wszystkich ciągów jednoznakowych, możemy …
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.