Насколько мощны CFG, которые допускают бесконечное количество правил?

Недавно я задавался вопросом, что произойдет, если мы позволим грамматикам без контекста иметь бесконечное количество правил. Ясно, что если бы мы допустили произвольные такие бесконечные наборы правил, каждый язык над некоторым алфавитом мог бы быть описан с помощью CFG с . Но что, если мы ограничим такими наборами правил, которые могут быть созданы с помощью контекстно-свободных грамматик?$L$$\Sigma$$G = (\{S\},\Sigma,R,S)$$R = \{S \rightarrow w \mid w \in L \}$$R$

Для этого, учитывая набор нетерминалов и терминалов , давайте рассмотрим правила не как элементы , а как строки над алфавитом . Теперь мой вопрос, если мы определим бесконечное правило CFG как кортеж где$N$$\Sigma$$N \times (N\cup \Sigma )^*$$R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$$G = (N, \Sigma, R, S)$

• $N$ - конечное множество нетерминалов
• $\Sigma$ это конечный алфавит
• $R$ - это набор правил вида с , таких, что существует некоторый CFG над с$A \rightarrow w$$A \in N$$w \in (N \cup \Sigma)^*$$G'$$R_{(N,\Sigma)}$$R = L(G')$
• $S \in N$ - начальный нетерминал

и мы определяем для таких бесконечных правил CFG, как это делается для CFG, какова связь между классом языков, генерируемых бесконечными правилами CFG (назовем этот класс ), классом контекстно-свободных языков а класс ?$L(G)$$irCF$$CF$$RE$

Очевидно, у нас есть , но является ли эквивалентным одному из этих классов (или некоторому другому классу)?$CF \subseteq irCF \subseteq RE$$irCF$

Предположим, мы берем метаграмму и разлагаем ее по двухсимвольным префиксам. Другими словами, для каждого конструкта , слева-производная над строкой . Это будет производить (конечное) множество (конечный) metagrammars, каждый из которых производит все (возможно , бесконечные) для некоторых производств .$G'$$A \in N$$G'_A$$G'$$A \to$$A \in N$

Теперь построим грамматику , правила которой являются объединением всех правил в грамматиках (с нетерминалами, переименованными во избежание столкновений), вместе с для каждого , где - начальный нетерминал для . для включают в себя и все нетерминалы для каждого ; начало не-терминала является началом не-терминал , и терминалы для в точности клеммы для . Я утверждаю (без доказательств), что$G''$$G'_A$$A \to S_{G'_A}$$G'_A$$S_{G'_A}$$G'_A$$G''$$N$$G'_A$$G$$G''$$G$$G''$является конечной грамматикой для того же языка, поскольку происхождение правил не влияет на процесс деривации; это просто подстановка строк над алфавитом.

Если приведенный выше план доказательства действителен, и одинаковы.$CF$$irCF$

Как я упоминал в комментарии, есть более интересные примеры двухуровневых грамматик, в том числе грамматик Ван Вейнгаардена и различных попыток создать более управляемый формализм без потери всей дополнительной мощности.