regras inúteis - Useless rules

Em ciência da computação teórica , em particular na teoria das linguagens formais , regras inúteis de uma gramática formal são as regras de produção simbólica que são inacessíveis ou improdutivo, ou seja, que podem ou não precisam de ser aplicadas.

Definição

Dada uma gramática livre de contexto , um não-terminal símbolo X é chamado produtivo , ou de geração , se houver uma derivação X ⇒ * w para alguma cadeia w de símbolos terminais. Um símbolo não-terminal X é chamado alcançável se houver uma derivação S ⇒ * α X β para algumas cadeias α, β de símbolos não-terminais e terminais, e em que S indica a gramática do símbolo de início .

Uma regra com um símbolo improdutiva ou inacessível em seu lado esquerdo pode ser excluído da gramática sem alterar a língua aceite (aka gerado). Da mesma forma, uma alternativa contendo um tal símbolo pode ser excluído do lado direito de uma regra sem alterar o idioma. Tais regras e alternativas são chamados inúteis .

Para gramáticas formais que são não livre de contexto , definições semelhantes se aplicam.

Exemplos

Denotando símbolos não-terminais e terminais por letras maiúsculas e minúsculas, respectivamente, na seguinte gramática regular com símbolo inicial S

S → Bb | cc | Ee
B → Bb | b
C → Cc | c
D → Bd | Cd | d
E → Ee

o não-terminal D é inacessível, e E é improdutiva. Assim, omitindo as duas últimas regras não muda a língua aceite pela gramática, nem omitindo a alternativa "| Ee " do lado direito da regra para S .

Limpeza Regras inúteis

Hopcroft, et al. dar um algoritmo para eliminar regras inúteis de uma gramática livre de contexto .

Aiken e Murphy dar um algoritmo fixpoint para detectar qual não terminais de uma determinada gramática de árvore regular são improdutivos.

Referências