Informatyka context-free

5

Jak udowodnić, że język nie jest pozbawiony kontekstu?

Dowiedzieliśmy się o klasie języków bezkontekstowych . Charakteryzuje się zarówno gramatykami bezkontekstowymi, jak i automatami pushdown, dzięki czemu łatwo jest pokazać, że dany język jest pozbawiony kontekstu.CFLCFL\mathrm{CFL} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że aby to zrobić, musielibyśmy wykazać dla wszystkich gramatyk (lub automatów), że nie potrafią …

88 formal-languages context-free proof-techniques reference-question

1

Pokaż, że {xy ∣ | x | = | y |, x ≠ y} jest pozbawione kontekstu

Pamiętam, że natrafiłem na następujące pytanie dotyczące języka, który podobno jest pozbawiony kontekstu, ale nie mogłem znaleźć dowodu na to. Czy może źle zapamiętałem pytanie? Tak czy inaczej, oto pytanie: Pokaż, że język jest wolne od kontekstu.L={xy∣|x|=|y|,x≠y}L={xy∣|x|=|y|,x≠y}L = \{xy \mid |x| = |y|, x\neq y\}

43 formal-languages context-free

2

Do czego odnosi się „kontekst” w „gramatyce bezkontekstowej”?

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ś może wyjaśnić, do czego contextodnosi się …

30 terminology context-free formal-grammars

3

Co tak naprawdę oznacza bezkontekstowa gramatyka bezkontekstowa?

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 pomóc?

29 terminology context-free formal-grammars

6

Generowanie kombinacji z zestawu par bez powtarzania elementów

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 …

28 algorithms graphics data-structures computational-geometry operating-systems process-scheduling algorithms sorting database-theory relational-algebra finite-model-theory logic automata linear-temporal-logic buchi-automata complexity-theory np-complete decision-problem machine-learning algorithms pattern-recognition logic formal-languages formal-grammars context-free

2

Jak udowodnić, że język jest pozbawiony kontekstu?

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 techniki znajdowania gramatyki bezkontekstowej dla danego języka? Dla stałych języków, …

26 formal-languages context-free formal-grammars proof-techniques reference-question

3

Czy język par słów o równej długości, których odległość hamowania wynosi 2 lub więcej, jest pozbawiona kontekstu?

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 połączenie dwóch słów o tej samej długości, których odległość młotkowania wynosi …

26 formal-languages context-free pushdown-automata pumping-lemma open-problem

4

Jak udowodnić, że gramatyka jest jednoznaczna?

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 } expression \mbox{ then } S …

25 context-free formal-grammars proof-techniques ambiguity

1

Zdecyduj, czy języki bezkontekstowe mogą być akceptowane przez deterministyczny automat przesuwania

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 gramatyki. Za pomocą jakiego algorytmu produkcji G możemy ustalić, czy D …

22 automata context-free pushdown-automata

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 …

21 formal-languages computability context-free computation-models context-sensitive

2

Czy języków bezkontekstowych w

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 ) = { ( m …

20 formal-languages reference-request context-free closure-properties

1

Czy można zadecydować o równości języka dla gramatyk liniowych bezkontekstowych?

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 liniowe, to problem jest rozstrzygalne, ponieważ obie opisują gramatyk regularnych języków.sol1sol1G_1sol2)sol2)G_2 …

19 formal-languages context-free formal-grammars

2

Czy mogą istnieć „martwe stany” w gramatyce bezkontekstowej?

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 generate a word. Is this allowed or MUST production rules end with an terminal at …

18 context-free automata formal-grammars

3

Algorytm sprawdzający, czy język jest pozbawiony kontekstu

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, który pomaga uczniom we wszystkich zadaniach domowych; …

18 algorithms formal-languages context-free decision-problem

1

Skonstruuj PDA jako uzupełnienie

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 ∗ }{ …

16 formal-languages automata context-free pushdown-automata

Pytania otagowane jako context-free