Pytania otagowane jako formal-grammars

Pytania dotyczące gramatyki formalnej, generatywne opisy języków formalnych.

2
Czy istnieją z natury niejednoznaczne i deterministyczne języki bezkontekstowe?
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 generują ten język, są dwuznaczne, a jednoznaczne inaczej. Przykładem deterministycznego, jednoznacznego języka jest język: Przykładem …
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 …
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, …
1
Czy istnieje jakiś nieogólny algorytm analizowania CFG, który rozpoznaje EPAL?
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 parsowania: jeszcze nie spotkałem się z żadnym algorytmem parsowania dla jednoznacznych CFG, które …
1
Jak pokazać, że L = L (G)?
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 pożądane słowa. Często możemy dyskutować na wysokim szczeblu, dlaczego …
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 …
1
Jak przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę?
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 przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę? Próbowałem zastąpić reguły przejścia …
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 …
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.