Final sentential forms

• https://arxiv.org/abs/2309.08719v1

sentential form, Turing power, recursively enumerable language, propagating context-free grammar, palindromial language, queue grammar

Nechť G je bezkontextová gramatika s totální abecedou V, a nechť F je finální jazyk nad abecedou W, jež je podmnožinou V. Finální větná forma je libovolná větná forma gramatiky G takové, že po vynechání symbolů z podabecedy V-W patří do jazyka F. Takový řetězec vzniklý eliminací všech neterminálů z W a patřící do F je v jazyce gramatiky G finalizovaném pomocí F když a jen když je složen pouze z terminálů. Jazyk generovaný bezkontextovou gramatikou finalizovaný regulárním jazykem je vždy bezkontextový. Na druhou stranu je dokázáno, že každý rekurzivně spočetný jazyk L lze popsat nevymazávající bezkontextovou gramatikou G takovou, že L je jazyk gramatiky G finalizovaný pomocí jazyka  {w#rev(w):řetězec w nad abecedou {0,1}}, kde rev(w) je reverzace řetězce w.