Главная arrow книги arrow Копия Глава 22. Общение arrow Порождающая мощь расширенных грамматик
Порождающая мощь расширенных грамматик

Каждое расширенное правило представляет собой схему правила, заменяющую собой множество правил, по одному для каждой возможной комбинации значений расширенных составляющих. Порождающая способность расширенных грамматик зависит от количества таких комбинаций. Если их количество является конечным, то расширенная грамматика эквивалентна контекстно-свободной грамматике: схема правила может быть заменена отдельными контекстно-свободными правилами. Если же количество значений бесконечно, то расширенные грамматики могут представлять языки, отличные от контекстно-свободных. Например, контекстно-зависимый языкможет быть представлен следующим образом: