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.

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
Pompujący lemat dla deterministycznych języków bezkontekstowych?
Lemat pompujący dla zwykłych języków może być użyty do udowodnienia, że ​​niektóre języki nie są regularne, a lemat pompujący dla języków bezkontekstowych (wraz z lematem Ogdena) może być użyty do udowodnienia, że ​​niektóre języki nie są kontekstowe. Czy istnieje determinujący lemat dla deterministycznych języków bezkontekstowych? To znaczy, czy istnieje lemat …
2
Język obejmujący liczbę niewymierną nie jest CFL
Pracuję nad ciężkim ćwiczeniem w podręczniku i po prostu nie mogę wymyślić, jak postępować. Oto problem. Załóżmy, że mamy język gdzie jest liczbą nieracjonalną. Jak mam udowodnić, że nie jest językiem bezkontekstowym?L={aibj:i≤jγ,i≥0,j≥1}L={aibj:i≤jγ,i≥0,j≥1}L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}γγ\gammaLLL W przypadku, gdy jest racjonalna, całkiem łatwo jest …
1
Czy parser Earleya można przekształcić w rozmyty parser podobny do Levenshtein Automata Algo dla DFA?
Istnieje sposób wykonywania rozmytego parsowania (akceptuje ciągi nawet w literówkach do określonej odległości edycji), z DFA i skonstruowanymi w czasie wykonywania automatami Levenshtein słowa wejściowego. Czy coś podobnego można zrobić z parserem Earley? Trudno mi zrozumieć algorytm, a co dopiero odpowiedzieć na to pytanie.
1
Konstruujesz wszystkie języki bezkontekstowe z zestawu języków podstawowych i właściwości zamknięcia?
Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego języka, języka zawierającego pusty ciąg i języków wszystkich ciągów jednoznakowych, możemy …
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 …
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
Język wartości funkcji afinicznej
Napisz n¯n¯\bar n dla dziesiętnego rozszerzenia nnn (bez wiodącego 0). Niech aaa i bbb będą liczbami całkowitymi o a>0a>0a > 0 . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Czy MMM regularne? bez kontekstu? (Kontrast z językiem wykresu funkcji afinicznej ) Myślę, że …
1
Jak można ws z | w | = | s | a my będziemy bez kontekstu, podczas gdy w # s nie jest?
Dlaczego (jeśli tak) separator ##\# robi różnicę między tymi dwoma językami? Powiedzmy: L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} Oto dowód i gramatyk reprezentującyLLL jak CFLCFLCFL A poniżej dodam dowód na to L#∉CFLL#∉CFLL_{\#} \notin CFL : Czy ##\#znak naprawdę …
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 …
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.