Pytania dotyczące gramatyki formalnej, generatywne opisy języków formalnych.
Ludzie często mówią, że parsery LR (k) są silniejsze niż parsery LL (k) . Te stwierdzenia są przez większość czasu niejasne; w szczególności, czy powinniśmy porównać klasy dla ustalonego kkk lub unii dla całego kkk ? Jak więc naprawdę wygląda sytuacja? W szczególności jestem zainteresowany tym, jak...
Nazwijmy bezkontekstowy język deterministyczny wtedy i tylko wtedy, gdy może on zostać zaakceptowany przez deterministyczny automat odpychający, a niedeterministyczny inaczej. Nazwijmy język bezkontekstowy z natury dwuznacznym wtedy i tylko wtedy, gdy wszystkie bezkontekstowe gramatyki, które...
Widząc, że w hierarchii Chomsky'ego języki Type 3 mogą być rozpoznawane przez maszynę stanową bez pamięci zewnętrznej (tj. Skończonego automatu), Type 2 przez maszynę stanową z pojedynczym stosem (tj. Automat push-down) i typ 0 przez automat stanowy z dwoma stosami (lub równoważnie taśmą, jak w...
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...
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 }...
EPAL, język parzystych palindromów, jest definiowany jako język generowany przez następującą jednoznaczną, bezkontekstową gramatykę: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL jest „zmorą” wielu algorytmów...
Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie...
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . Szukam teorii matematycznych, które zajmują się opisywaniem języków formalnych (zestawu ciągów) w...
Dlaczego w konstrukcji kompilatora należy wyeliminować lewą rekurencję w gramatyce? Czytam, że dzieje się tak, ponieważ może powodować nieskończoną rekurencję, ale czy nie jest to prawdą również w przypadku prawidłowej gramatyki
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...
Zgodnie z tym artykułem Wikipedii , nieograniczone gramatyki są równoważne maszynom Turinga. Artykuł zauważa, że mogę przekonwertować dowolną maszynę Turinga na nieograniczoną gramatykę, ale pokazuje ona tylko, jak przekonwertować gramatykę na maszynę Turinga. Jak rzeczywiście to zrobić i...
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...
Jeśli mam gramatykę typu 3, można ją przedstawić na automacie wypychania (bez wykonywania żadnych operacji na stosie), dzięki czemu mogę reprezentować wyrażenia regularne przy użyciu języków bezkontekstowych. Ale czy mogę wiedzieć, czy gramatyka typu 3 to , , itd. Bez konstruowania jakichkolwiek...
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ą...
Można argumentować, że większość języków stworzonych do opisywania codziennych problemów ma charakter kontekstowy. Z drugiej strony jest możliwe i nietrudno znaleźć niektóre języki, które nie są rekurencyjne, a nawet nie są wymienne. Pomiędzy tymi dwoma typami znajdują się rekurencyjne języki...
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...
Zgodnie z artykułem Wikipedii , L w oznacza „skanowanie od lewej do prawej”, a „R” oznacza „pochodzenie od prawej”. Jednak w oryginalnym artykule Knutha na temat gramatyki definiuje (na stronie 610) jako język, który jest „możliwy do przetłumaczenia z lewej na prawą za pomocą związanego ”.L R ( k...