Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

1
Jaka jest domniemana zależność między językami P (PTime) i Type 1 (kontekstowymi)?
Nie wiadomo czy P⊆CSLP⊆CSLP\subseteq CSL lub P⊈CSLP⊈CSLP\not\subseteq CSL, gdzie PPP jest zbiorem wszystkich języków rozstrzygalnych w czasie wielomianowym na deterministycznej maszynie Turinga, oraz CSLCSLCSL jest klasą języków kontekstowych, znanych jako równoważne NSPACE(O(n))NSPACE(O(n))NSPACE(O(n)) , języki ustalane przez automaty ograniczane liniowo. W przypadku wielu otwartych pytań istnieje tendencja do jednej odpowiedzi ( …
3
Trudność ze znalezieniem co najwyżej słowa
Opis problemu: Pozwolić MMM być (potencjalnie niedeterministycznym) automatem wypychającym i pozwól AA\cal Abyć jego alfabetem wejściowym. Czy jest jakieś słowo?w∈A∗w∈A∗w \in \cal A^* św |w|≤k|w|≤k|w| \leq k które jest akceptowane przez MMM ? Czy ten problem NP-jest kompletny? Czy zostało to zbadane? Czy istnieje algorytm pozwalający znaleźć takie słowo?
1
Czy istnieje metoda udowodnienia nieregularności transformacji łańcucha?
Istnieje wiele różnych modeli definiowania transformacji między językami. Przetworniki stanu skończonego i transformacje grafu definiowane przez MSO na grafach łańcuchowych to dwa, z którymi najlepiej się znam. Wiemy, że dwudrożne przetworniki stanu skończonego (które są bardziej ekspresyjne niż ich jednokierunkowe odpowiedniki) i transformacje ciągów definiowane przez MSO przechwytują ten sam …
1
Uogólnienie stwierdzenia, że ​​monoid rozpoznaje język iff monoid syntaktyczny dzieli monoid
Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to ML=φ−1(φ(L)))L=φ−1(φ(L)))L = \varphi^{-1}(\varphi(L))) Mamy więc ładny wynik: Monoid rozpoznaje jeśli jest homomorficznym obrazem submonoidu (napisanego jako …
1
Asymptotyczna gęstość niejednoznacznych gramatyk bezkontekstowych (CFG)
Jaki jest stosunek niejednoznacznych CFG do wszystkich CFG ? Ponieważ oba zestawy są w nieskończoność nieskończone, stosunek nie jest dobrze zdefiniowany. Ale co z asymptotyczną gęstością : limn ↦ ∞# niejednoznaczny CFG o rozmiarze < n# CFG o wielkości < nlimn↦∞# niejednoznaczny CFG wielkości<n# CFG wielkości<n\lim_{n \mapsto \infty}\frac {\# \text{ …
3
Pośrednie przykłady z formalnej teorii języka
Uczę się algebraicznej teorii parsowania. Moim pierwszym problemem jest zidentyfikowanie przykładów semieralnych, które są specyficzne dla formalnej teorii języka. Oto próba skonstruowania dwóch przykładów. 1 Biorąc pod uwagę gramatykę CNF, elementy semeryzacji są zestawami symboli terminalnych i nieterminalnych z operacjami: i) Mnożenie , łączenie dwóch zestawów parami zgodnie z regułą …
1
Wyrażenia regularne bez zmian
Zastanawiałem się, jakie zestawy języków są generowane przez ograniczenia wyrażeń regularnych. Załóżmy, że wszystkie ograniczenia mają stały symbol dla każdego elementuΣΣ\Sigmai konkatenacja. Następnie można utworzyć osiem klas poprzez obecność lub brak dopełniacza / negacji, zmiany / unii i gwiazdy Kleene. (Tak, „normalne” wyrażenia regularne nie majądoC^C operator, ale tutaj jest …
1
Czy istnieje wielomianowy rozmiar CFG opisujący ten skończony język?
Czy istnieją permutacje i wielkość wielomianowa (w ) gramatyka bezkontekstowa opisująca język skończony zamiast alfabetu ?π1,π2π1,π2\pi_1,\pi_2|w|=n|w|=n|w|=n{wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{0,1}{0,1}\{0,1\} AKTUALIZACJA: Dla jednej permutacji jest to możliwe. jest odwróceniem lub względnie niewielką modyfikacją odwrócenia.ππ\piππ\pi
4
Dlaczego automaty z ograniczeniem liniowym nie są tak popularne jak inne automaty?
Z mojego doświadczenia wynika, że ​​języki kontekstowe i automaty z ograniczeniami liniowymi są często pomijane lub przewijane na kursach teorii obliczeń, a nawet są pomijane w niektórych znaczących podręcznikach, chociaż automaty skończone i zmniejszające są bardzo popularne. Z pewnością musi istnieć dobry powód, dla którego LBA są mniej skoncentrowane niż …
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.