Quão poderosos são os CFGs que permitem um número infinito de regras?

Eu estava pensando recentemente o que aconteceria se permitíssemos que as gramáticas sem contexto tivessem um número infinito de regras. Claramente, se permitirmos arbitrários conjuntos infinitos de regras, todo idioma sobre algum alfabeto poderia ser descrito por um CFG com . Mas e se restringirmos a esses conjuntos de regras que podem ser criadas por gramáticas livres de contexto?$L$$\Sigma$$G = (\{S\},\Sigma,R,S)$$R = \{S \rightarrow w \mid w \in L \}$$R$

Para esse propósito, dado um conjunto de não terminais e terminais , vamos ver as regras não como elementos de , mas como cadeias de caracteres sobre o alfabeto . Agora, minha pergunta é: se definirmos uma regra infinita CFG como uma tupla em que$N$$\Sigma$$N \times (N\cup \Sigma )^*$$R_{(N,\Sigma)} = N \cup \Sigma \cup \{\rightarrow\}$$G = (N, \Sigma, R, S)$

• $N$ é um conjunto finito de não-terminais
• $\Sigma$ é um alfabeto finito
• $R$ é um conjunto de regras no formato com , modo que exista algum CFG sobre com$A \rightarrow w$$A \in N$$w \in (N \cup \Sigma)^*$$G'$$R_{(N,\Sigma)}$$R = L(G')$
• $S \in N$ é o não-terminal inicial

e definimos para CFGs de regras infinitas, assim como é feito para CFGs, qual é a relação entre a classe de idiomas gerada por CFGs de regras infinitas (vamos chamar de classe ), a classe de linguagens livres de contexto e a classe ?$L(G)$$irCF$$CF$$RE$

Obviamente, temos , mas o é equivalente a uma dessas classes (ou alguma outra classe)?$CF \subseteq irCF \subseteq RE$$irCF$

Suponha que tomemos o metagrama e o fatoremos com prefixos de dois símbolos. Em outras palavras, para cada constrói , a derivada esquerda de sobre a string . Isso irá produzir um (finito) conjunto de (finitos) metagrammars, cada uma produzindo todas as produções (possivelmente infinito) para alguns .$G'$$A \in N$$G'_A$$G'$$A \to$$A \in N$

Agora, construa a gramática , cujas regras são a união de todas as regras nas gramáticas (com terminais não renomeados para evitar colisões), juntamente com para cada , onde é o terminal não terminal para . Os não terminais para incluem e todos os não terminais para cada ; o início não-terminal é o início não-terminal de , e os terminais de são, precisamente, os terminais de . Afirmo (sem prova) que$G''$$G'_A$$A \to S_{G'_A}$$G'_A$$S_{G'_A}$$G'_A$$G''$$N$$G'_A$$G$$G''$$G$$G''$é uma gramática finita para o mesmo idioma, pois o processo de derivação não é afetado pela origem das regras; é apenas uma substituição de string sobre um alfabeto.

Se o esquema de prova acima for válido, e são os mesmos.$CF$$irCF$

Como aludi em um comentário, existem exemplos mais interessantes de gramáticas de dois níveis, incluindo gramáticas de Van Wijngaarden e as várias tentativas feitas para criar formalismos mais gerenciáveis, sem perder todo o poder adicional.