Rekursiv grammatik - Recursive grammar

I datalogi kaldes en grammatik uformelt en rekursiv grammatik, hvis den indeholder produktionsregler, der er rekursive , hvilket betyder, at udvidelse af en ikke-terminal i henhold til disse regler til sidst kan føre til en streng, der inkluderer den samme ikke-terminal igen. Ellers kaldes det en ikke-rekursiv grammatik .

For eksempel kan en grammatik for en kontekst-fri sprog er efterladt rekursiv hvis der findes en ikke-terminalt symbol A , der kan sættes igennem de regler for produktion til at producere en streng med A (som det yderste venstre symbol). Alle typer grammatikker i Chomsky-hierarkiet kan være rekursive, og det er rekursion, der tillader produktion af uendelige sæt ord.

Ejendomme

En ikke-rekursiv grammatik kan kun producere et begrænset sprog; og hvert endeligt sprog kan produceres ved en ikke-rekursiv grammatik. For eksempel producerer en lineær grammatik blot et enkelt ord.

En rekursiv kontekstfri grammatik, der ikke indeholder unyttige regler, producerer nødvendigvis et uendeligt sprog. Denne egenskab danner grundlaget for en algoritme, der effektivt kan teste, om en kontekstfri grammatik producerer et begrænset eller uendeligt sprog.

Referencer