Pytania otagowane jako formal-grammars

Pytania dotyczące gramatyki formalnej, generatywne opisy języków formalnych.

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
Jaka jest ta gramatyka LL (1)?
To pytanie z Dragon Book. Oto gramatyka: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon Pytanie dotyczy tego, jak pokazać, że jest to LL (1), ale nie SLR (1). Aby udowodnić, że jest to LL (1), próbowałem zbudować jego tabelę analizującą, ale otrzymuję wiele produkcji w komórce, …
1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
2
Jak mogę udowodnić, że ten język nie jest pozbawiony kontekstu?
Mam następujący język {0i1j2k∣0≤i≤j≤k}{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} Próbuję ustalić, do której klasy języka Chomsky pasuje. Widzę, jak można to zrobić za pomocą gramatyki kontekstowej, więc wiem, że jest przynajmniej wrażliwa na kontekst. Wydaje się, że nie byłoby możliwe stworzenie gramatyki bezkontekstowej, ale …
1
Analiza składni z przesunięciem - pytania
Ostatnio natknąłem się na artykuł opisujący technikę parsowania wspomnianą w tytule. Niestety terminologia zastosowana we wspomnianym artykule jest nieco poza moim zrozumieniem, więc starałem się zrozumieć algorytm konstrukcji bardziej intuicyjnie. Wierzę, że mi się udało ( ta prezentacja była źródłem momentu ah-ha), ale doceniona zostanie weryfikacja poprawności przez kogoś, kto …
3
Rozważalne języki i nieograniczone gramatyki?
Maszyny Turinga i nieograniczona gramatyka to dwa różne formalizacje, które definiują języki RE. Niektóre języki RE są rozstrzygalne, ale nie wszystkie są. Możemy zdefiniować rozstrzygalne języki za pomocą maszyn Turinga, mówiąc, że dany język jest rozstrzygalny, jeśli istnieje TM dla języka, który zatrzymuje i akceptuje wszystkie ciągi w języku oraz …
1
Biorąc pod uwagę ciąg i CFG, jakie znaki mogą podążać za ciągiem (w sentymentalnych formach CFG)?
Niech ΣΣ\Sigma będzie zbiorem terminali, a NNN zbiorem nieterminalnych symboli gramatyki bez kontekstu GGG. Powiedzieć, że posiada ciąg a∈(Σ∪N)+a∈(Σ∪N)+a \in (\Sigma \cup N)^+ taki, że w którym i są zdaniowymi formy .x , y ∈ ( Σ ∪ N ) ∗ S ( G ) Gxay∈S(G)xay∈S(G)x a y \in \mathcal{S}(G)x,y∈(Σ∪N)∗x,y∈(Σ∪N)∗x,y\in …
5
Czy istnieje znana metoda konstruowania gramatyki przy skończonym zestawie skończonych łańcuchów?
Z mojego czytania wynika, że ​​większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda wykonania tego? Idealnie nazwa techniki, którą mogę badać. Alternatywnie, …
2
Czy istnieje inna rozdzielczość problemu „zwisające inaczej” niż „najbliższy odpowiednik”?
Poniższa gramatyka bezkontekstowa przedstawia dwuznaczność typu „wiszące inne” (wyobraź to sobie zaaaoznacza if expr thenibbboznacza elseidocc oznacza inny rodzaj instrukcji lub bloku): S.→ a S.b S.|a S.|doS→aSbS|aS|c \begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned} Na przykład, a a c b caacbcaacbc może być analizowany jako ( ( C …
1
Jak potężne są CFG, które pozwalają na nieskończoną liczbę zasad?
Zastanawiałem się ostatnio, co by się stało, gdybyśmy pozwolili gramatykom bezkontekstowym mieć nieskończoną liczbę reguł. Oczywiście, gdybyśmy zezwolili na arbitralne takie nieskończone zbiory reguł, każdy językLLL nad jakimś alfabetem ΣΣ\Sigma może być opisany przez CFG G=({S},Σ,R,S)G=({S},Σ,R,S)G = (\{S\},\Sigma,R,S) z R={S→w∣w∈L}R={S→w∣w∈L}R = \{S \rightarrow w \mid w \in L \}. Ale …
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
1
Konwertuj CFG na PDA
Czy istnieje zestaw reguł lub metod służących do konwersji gramatyki bezkontekstowej na automaty wypychające? Znalazłem już kilka slajdów w Internecie, ale nie byłem w stanie ich zrozumieć. W slajdzie 10 mówi o niektórych zasadach, czy ktokolwiek mógłby to wyjaś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.