Rekursive Grammatik - Recursive grammar

In der Informatik , eine Grammatik ist informell eine gerufene rekursive Grammatik , wenn es enthält Produktionsregeln , die rekursiv , so dass schließlich an diesen Regeln eine nicht-Endgerät nach Erweiterung kann zu einem String führen , die wiederum den gleichen Nicht-Terminal umfasst. Andernfalls wird es als nicht rekursive Grammatik bezeichnet .

Zum Beispiel kann eine Grammatik für eine kontextfreie Sprache ist linksrekursiv wenn ein Nicht-Terminal - Symbol vorhanden ist A , die durch die Produktionsregeln gesetzt werden kann eine Zeichenfolge mit produzieren A (wie dem am weitesten links stehenden Symbol). Alle Arten von Grammatiken in der Chomsky-Hierarchie können rekursiv sein, und es ist die Rekursion, die die Erzeugung unendlicher Sätze von Wörtern ermöglicht.

Eigenschaften

Eine nicht rekursive Grammatik kann nur eine endliche Sprache erzeugen; und jede endliche Sprache kann durch eine nicht rekursive Grammatik erzeugt werden. Beispielsweise erzeugt eine geradlinige Grammatik nur ein einziges Wort.

Eine rekursive kontextfreie Grammatik, die keine nutzlosen Regeln enthält , erzeugt notwendigerweise eine unendliche Sprache. Diese Eigenschaft bildet die Grundlage für einen Algorithmus , der effizient testen kann, ob eine kontextfreie Grammatik eine endliche oder unendliche Sprache erzeugt.

Verweise