One-Sided Random Context Grammars: A Survey

Připomeňme, že pojem jednastránné gramatiky s nahodilým kontextem je založen na konečném počtu bezkontextových pravidel, která jsou doplněna konečným počtem povolujících a zakazujících neterminálních symbolů. Množina těchto pravidel je rozdělena na dvě - množinu zleva nahodilých pravidel a množinu zprava nahodilých pravidel. Když aplikujeme zleva nahodilé pravidlo, gramatika zkontroluje existenci povolujících a absenci zakazujících neterminálů v prefixu nalevo od přepisovaného neterminálu. Analogicky při aplikaci zprava nahodilého pravidla je kontrolována existence povolujících a absence zakazujících symbolů v sufixu napravo od přepisovaného neterminálu.

Tato kapitola v knize dává přehled dosažených výsledků pro tyto jednostranné gramatiky s nahodilým kontextem. Tyto výsledky se týkají generativní síly, normálních forem, redukce velikosti a koncepčních modifikací, které jsou omezujícími či zobecňujícími verzemi těchto gramatik. Pravděpodobně nejzájímavější výsledek říká, že jednostranné gramatiky s nahodilým kontextem bez vymazávajících pravidel charakterizují třídu kontextových jazyků a s vymazávajícími pravidly charakterizují třídu rekurzivně spočetných jazyků, z čehož plyne, že jsou tyto gramatiky silnější než klasické gramatiky s nahodilým kontextem. Dále je navrženo studium řady otevřených problémů.