Pytania dotyczące zestawu języków (równoważnie) opisanych przez gramatyki bezkontekstowe lub zaakceptowanych przez (niedeterministyczne) automaty wypychające.
Istnieje wiele definicji online na temat gramatyki bezkontekstowej, ale nic, co znalazłem, nie zaspokoi mojego głównego problemu: Z jakiego kontekstu jest wolny? Aby to zbadać, przejrzałem „gramatykę wrażliwą na kontekst”, ale nadal nie udało mi się znaleźć o co chodzi w „kontekście”. Czy ktoś...
Przez jakiś czas studiowałem kompilatory i szukałem, co rozumie się przez „kontekst” w gramatyce i co to znaczy, że gramatyka jest „bezkontekstowa”, ale bez rezultatu. Czy ktoś może w tym
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita nie była...
Istnieje wiele technik, aby udowodnić, że język nie jest pozbawiony kontekstu, ale jak udowodnić, że język jest pozbawiony kontekstu? Jakie są techniki, aby to udowodnić? Oczywiście jednym ze sposobów jest wykazanie gramatyki bezkontekstowej dla tego języka. Czy istnieją jakieś systematyczne...
Czy następujący kontekst językowy jest bezpłatny? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Jak wskazał sdcvvc, słowo w tym języku można również opisać jako...
Mój problem polega na tym, jak mogę udowodnić, że gramatyka jest jednoznaczna? Mam następującą gramatykę: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if }...
Biorąc pod uwagę bezkontekstową gramatykę G, istnieje niedeterministyczny automat pushdown N, który akceptuje dokładnie język, który akceptuje G. (i odwrotnie) Nie może również istnieć deterministyczny automat ze stosem D, który akceptuje dokładnie język G akceptuje też. To zależy od...
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...
Wiemy, że języki bezkontekstowe nie są zamknięte pod uzupełnieniem. O ile mi zrozumieć, języków bezkontekstowych, które są podzbiorem * b * dla niektórych liter a , b są zamknięte pod dopełniacza (!?)a∗b∗a∗b∗a^*b^*a,ba,ba,b Oto mój argument. Każdy język CF ma półliniowy obraz Parikha π ( L ) = {...
Rozważmy dwa gramatyk bezkontekstowych i i zadać następujące pytanie: Czy , czyli są dwa równoważne gramatyki?sol1sol1G_1sol2)sol2)G_2L ( G1) = L ( G2))L.(sol1)=L.(sol2))L(G_1) = L(G_2) Ogólnie problem ten jest nierozstrzygalny. Jednakże, jeśli zarówno i są liniowe lewej (lub prawej) Gramatyki...
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest pozbawiony kontekstu? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak ), sprawdź, czy język jest pozbawiony kontekstu, czy nie . Wyobraź sobie, że piszemy serwis internetowy,...
Czy gramatyka bezkontekstowa może zawierać „martwe stany” z automatu, np G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G=({a,b,c},{A,B,C},{A→aB,B→b,B→C,C→cC},A)?G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,? B→CB→CB\to CC→cCC→cCC\to cC will loop forever and never...
Zastanawiam się, czy to w ogóle możliwe, ponieważ . Dlatego PDA, który potrafi odróżnić słowo od reszty równie dobrze może je zaakceptować , co wydaje mi się sprzeczne. w ∈ { a n b n c n ∣ n ≥ 0 } { a ∗ b ∗ c ∗ }{ anbndon∣ n ≥ 0 } ∉ C F L{zanbndon∣n≥0}∉dofaL.\{a^n b^n c^n \mid n \geq 0\} \not\in...
Mówi się, że przecięcie języka L bez kontekstu z językiem zwykłym M jest zawsze wolne od kontekstu. Zrozumiałem dowód na konstrukcję wielu produktów, ale wciąż nie rozumiem, dlaczego nie zawiera kontekstu, ale nie jest regularny. Język generowany przez takie skrzyżowanie ma ciągi znaków, które są...
Uwaga: jest to pytanie związane z nauką na kursie CS na uniwersytecie, NIE jest to zadanie domowe i można je znaleźć tutaj pod egzaminem Fall 2011. Oto dwa pytania, na które patrzę z poprzedniego egzaminu. Wydaje się, że są ze sobą powiązane, pierwsze: Pozwolić F I N I T EC F G= {...
Tak więc w zasadzie L spełnia warunki pompowania lematu dla CFL, ale nie jest CFL (jest to możliwe zgodnie z definicją
Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?LLLL={a,b}∗−{ww∣w∈{a,b}∗}L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}LLLLLL Próbowałem przeciąć z , ale nadal nie mogę niczego...
Niech GGG będzie gramatyką bezkontekstową. Łańcuch zacisków i nieterminali z GGG mówi się zdań tworzą z GGG , czy można go otrzymać stosując produkcje GGG zero lub więcej razy symbolu startu SSS . Niech SF(G)SF(G)\operatorname{SF}(G) będzie zbiorem form zdaniowych GGG . Niech...
Wiem, że istnieją nieregularne języki, więc jest regularny, ale wszystkie przykłady, które mogę znaleźć, są zależne od kontekstu, ale nie pozbawione kontekstu.L.∗L∗L^* Jeśli nie ma, jak to
Mam problem z tym ćwiczeniem: Niech G będzie następującą dwuznaczną gramatyką dla rachunku λ: E → v | λv.E | EE | (E) gdzie E jest pojedynczym nieterminalnym symbolem, λv.E oznacza abstrakcję względem zmiennej v w E, a EE oznacza aplikację. Zdefiniuj gramatykę LL (1) G ′, tak aby L...