One-Sided Random Context Grammars

Řízené přepisování, gramatiky s nahodilým kontextem, jednostranné varianty, generativní síla, jazykové třídy

Článek zavádí jednostranné gramatiky s nahodilým kontextem, což jsou bezkontextové gramatiky, kde je navíc ke každému pravidlu přiřazena množina povolujících neterminálů a množina zakazujících neterminálů. Množina pravidel je u těchto gramatik dále rozdělena na množinu levě nahodilých kontextových pravidel a pravě nahodilých kontextových pravidel. Levě nahodilé kontextové pravidlo může přepsat neterminál ve větné formě pouze tehdy, když se vlevo od něj vyskytují všechny povolující neterminály a všechny zakazujícící neterminály se na tomto místě nevyskytují. Pravě nahodilá kontextová pravidla jsou aplikována obdobně, ovšem s tím rozdílem, že se na výskyt symbolů díváme doprava od přepisovaného neterminálu.

V článku je demonstrováno, že pokud v těchto gramatikách nepřipustíme vymazávácí pravidla, tak definují třídu kontextových jazyků. Při připuštění těchto pravidel definují třídu rekurzivně spočetných jazyků. Je ukázáno, že tyto výsledky platí i v případě, když je množina levě nahodilých kontextovým pravidel totožná s množinou pravě nahodilých kontextových pravidel. Článek dále diskutuje generativní sílu různých speciálních variant těchto gramatik. V závěru jsou zmíněny některé důležité otevřené problémy k budoucímu studiu.