Pytania otagowane jako context-sensitive

1
Maszyny dla języków bezkontekstowych, które nie zyskują dodatkowej mocy z niedeterminizmu
Rozważając modele maszynowe obliczeń, hierarchię Chomsky'ego zazwyczaj charakteryzuje (w kolejności), automat skończony, automat push-down, automat liniowo związany i maszyny Turinga. W przypadku pierwszego i ostatniego poziomu 1 (języki zwykłe i języki z wyliczaniem rekurencyjnym) nie ma różnicy w sile modelu, czy rozważamy maszyny deterministyczne czy niedeterministyczne, tj. DFA są równoważne …
2
Czy wszystkie języki kontekstowe są rozstrzygalne?
Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to: Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią. Widziałem, że automat ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli …
4
Czy ktoś może podać prosty, ale nie zabawkowy przykład gramatyki kontekstowej?
Próbuję zrozumieć gramatyki kontekstowe. Rozumiem, dlaczego języki lubią { w w ∣ w ∈ A∗}{ww∣w∈ZA∗}\{ww \mid w \in A^*\} { anbndon∣ n ∈ N }{zanbndon∣n∈N.}\{a^n b^n c^n \mid n\in\mathbb{N}\} nie są wolne od kontekstu, ale co chciałbym wiedzieć, jeśli język podobny do niepisanego rachunku lambda jest wrażliwy na kontekst. Chciałbym …
3
Gramatyka kontekstowa dla języka słów połączonych ze sobą
Szukam gramatyki kontekstowej opisującej następujący język: .L={ww∣w∈{a,b}∗,|w|≥1}L={ww∣w∈{a,b}∗,|w|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} Mam problem z tym, że żadne reguły, takie jak są dozwolone i dlatego nie mogę umieścić żadnego nieterminala wskazującego „środek” słowa. Czy jest jakiś sposób na rozwiązanie tego problemu?X→εX→εX \to \varepsilon
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.