Pytania otagowane jako fl.formal-languages

języki formalne, gramatyka, teoria automatów

1
Czy istnieje książka / artykuł przeglądowy przedstawiający hierarchie klas językowych, właściwości zamknięcia itp
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce lub opracowaniu, które opisuje właściwości tych języków. Większość tego, na …
3
„Prosty” język poza
Szukam języka L o następujących właściwościach: L nie powinien być pozbawiony kontekstu. Uzupełnienie L nie powinno być pozbawione kontekstu. (Wszystko, co widzisz w podręcznikach jako główny przykład języków bezkontekstowych, wydaje się nie spełniać tego drugiego wymogu). L nie powinien być zbyt trudny. Na przykład wiem, że nierozstrzygalne języki spełniają dwa …
1
Jakie formalne klasy językowe to XML i JSON z unikalnymi kluczami?
Przeniosłem to pytanie z stackoverflow, gdzie id nie otrzymał odpowiedzi. Mieliśmy podobne pytanie, czy JSON jest regularny : JSON i XML są często nazywane językami bezkontekstowymi - oba są określone głównie przez gramatykę formalną w EBNF. Jednak dotyczy to tylko JSON zdefiniowanego w RFC 4329, sekcja 2.2, który nie wymaga …
2
Czy dany język regularny zawiera nieskończony podzbiór bez prefiksów?
Zestaw słów nad skończonym alfabetem nie zawiera prefiksu, jeśli nie ma dwóch odrębnych słów, w których jedno jest prefiksem drugiego. Pytanie brzmi: Jaka jest złożoność sprawdzania, czy zwykły język podany jako NFA zawiera nieskończony podzbiór bez prefiksów? Odpowiedź (z powodu Michaiła Rudoya, tutaj poniżej) : Można to zrobić w czasie …
1
Jaka jest nazwa funkcji
Niech będzie językiem if : Σ ⋆ × Σ ⋆ → Σ ⋆ funkcja na dwóch parametrach z właściwością, która dla wszystkich x i y , f zwraca element L wtedy i tylko wtedy, gdy oba x i y są elementami L :LL.Lf:Σ⋆×Σ⋆→Σ⋆fa:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starxxxyyyffafLLLxxxyyyLLL f(x,y)∈L⟺x∈L∧y∈L.f(x,y)∈L⟺x∈L∧y∈L.f(x,y)\in L \iff x\in L\wedge y\in …
3
Dwuznaczność w zwykłych i pozbawionych kontekstu językach
Rozumiem następujące twierdzenia, które są prawdziwe: Dwie różne pochodne łańcucha w danym CFG mogą czasem przypisywać to samo drzewo parsowania łańcuchowi. Kiedy w danym CFG występują pochodne jakiegoś łańcucha, które przypisują różne drzewa parsowania, CFG jest niejednoznaczny. Niektóre języki bezkontekstowe generowane przez niejednoznaczne CFG są również generowane przez jednoznaczne CFG. …
2
Na
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie 4: wymiarową afinicznej kolektor jest do ekspresji w skończonej związek rozdzielaczy …
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.