W wielu artykułach dotyczących gramatyk bezkontekstowych (CFG), przykłady takich gramatyk tam często dopuszczają łatwą charakterystykę generowanego języka. Na przykład: S →S→aaSbS.→zazaS.bS \to a a S b S→S.→S \to generuje ,{a2ibi|i≥0}{za2)jabja|ja≥0}\{ a^{2i} b^i | i \geq 0\} S → a a S b...
Zastanawiam się, czy są jakieś dokumenty lub badania dotyczące widocznych automatów przesuwających w dół, ale pozwalające na wypychanie słów zamiast pojedynczych liter na stos. Alternatywnie, konstrukcja umożliwiająca wypychanie symboli na -transitions może osiągnąć ten sam...
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie...
Niech będzie językiem bezkontekstowym. Zdefiniować p p c ( L ) za przed i przyrostek zamknięcie L , innymi słowy, p p c ( L ) obejmują L jest prefiks i postfixes i stąd L siebie. Moje pytanie: jeśli L jest pozbawiony kontekstu i ma niejednoznaczną gramatykę, to czy to samo dotyczy p p c ( L )...