Gramatică recursivă - Recursive grammar

În informatică , o gramatica este numit informal o gramatica recursiv în cazul în care conține reguli de producție , care sunt recursiv , ceea ce înseamnă că extinderea unei conform neterminală acestor reguli poate duce în cele din urmă la un șir de caractere care include aceeași non-terminal din nou. Altfel se numește gramatică nerecursivă .

De exemplu, o gramatică pentru un limbaj fără context este lăsată recursivă dacă există un simbol non-terminal A care poate fi pus prin regulile de producție pentru a produce o șir cu A (ca simbolul din stânga). Toate tipurile de gramatică din ierarhia Chomsky pot fi recursive și este recursivitatea care permite producerea de seturi infinite de cuvinte.

Proprietăți

O gramatică nerecursivă poate produce doar un limbaj finit; și fiecare limbaj finit poate fi produs de o gramatică nerecursivă. De exemplu, o gramatică liniară produce doar un singur cuvânt.

O gramatică recursivă fără context care nu conține reguli inutile produce în mod necesar un limbaj infinit. Această proprietate constituie baza unui algoritm care poate testa eficient dacă o gramatică fără context produce un limbaj finit sau infinit.

Referințe