Pytania otagowane jako context-free

Pytania dotyczące zestawu języków (równoważnie) opisanych przez gramatyki bezkontekstowe lub zaakceptowanych przez (niedeterministyczne) automaty wypychające.

1
Jak zrekonstruować las drzew składniowych z wektora Earley?
Użycie wektora Earleya jako rozpoznającego jest dość proste: po osiągnięciu końca struny wystarczy sprawdzić, czy produkcja aksjomatyczna została rozpoczęta w pozycji 0. Jeśli masz przynajmniej jeden ciąg, łańcuch jest akceptowany. Użycie wektora Earleya do odtworzenia drzewa przetwarzania jest mniej oczywiste. Właściwie nie jestem w stanie ustalić, jak mogłaby działać procedura …
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ć?
2
Dwustanowa maszyna Turinga do dopasowywania nawiasów
Na studiach poznawaliśmy ogólnie teorię obliczeń, a dokładniej maszyny Turinga. Jednym z wielkich wyników teoretycznych jest to, że kosztem potencjalnie dużego alfabetu (symboli) można zmniejszyć liczbę stanów do zaledwie 2. Szukałem przykładów różnych maszyn Turinga, a częstym przedstawionym przykładem jest dopasowywanie / sprawdzanie nawiasów. Zasadniczo sprawdza, czy ciąg nawiasów, np. …
1
Czy następująca transformacja zachowuje płynność kontekstową?
Napotkałem ten problem związany z manipulowaniem językiem bezkontekstowym. Niech będzie językiem bezkontekstowym. Zdefiniuj dla każdego . Czy zawsze jest pozbawione kontekstu? Domyślam się, że zachowa kontekstowość. Czy ktoś może przedstawić podstawowy dowód na to?LL.LL#={x:xi∈LL.#={x:xja∈L.L^{\#} = \{ x : x^i \in Li=0,1,2,...}ja=0,1,2),...}i=0,1,2,...\}L#L.#L^{\#}
1
Udowodnij to
Chciałbym skorzystać z Twojej pomocy przy następującym problemie: L = { ⟨ M⟩ ∣ L ( M) jest pozbawiony kontekstu }L={⟨M⟩∣L(M) is context-free}L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \} . Pokaż, że .L ∉ R E∪ C.o R EL∉RE∪CoREL \notin RE \cup CoRE Wiem, że aby udowodnić , wystarczy znaleźć …
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.