gramática recursiva - Recursive grammar

Em ciência da computação , a gramática é informalmente chamado de gramática recursiva se ele contém regras de produção que são recursiva , o que significa que a expansão de um não-terminal de acordo com estas regras pode eventualmente levar a uma cadeia que inclui o mesmo não terminal novamente. Caso contrário, ele é chamado de gramática não-recursiva .

Por exemplo, uma gramática para uma linguagem livre de contexto é deixado recursiva se existe um símbolo não-terminal A que pode ser colocada através das regras de produção para produzir uma string com A (como o símbolo mais à esquerda). Todos os tipos de gramáticas na hierarquia de Chomsky pode ser recursiva e é recursão que permite a produção de conjuntos infinitos de palavras.

propriedades

A gramática não-recursiva pode produzir apenas uma linguagem finita; e cada língua finito pode ser produzido por uma gramática não-recursiva. Por exemplo, uma gramática linear produz apenas uma única palavra.

Uma gramática livre de contexto recursivo que não contém regras inúteis produz necessariamente uma linguagem infinita. Esta propriedade é a base para um algoritmo que pode testar de forma eficiente se uma gramática livre de contexto produz uma linguagem finito ou infinito.

Referências