Deterministisch kontextfreie Sprache

Eine deterministisch kontextfreie Sprache ist eine Sprache, die von einem deterministischen Kellerautomaten akzeptiert wird. Manchmal wird auch der gekürzte Begriff deterministische Sprache verwendet. Im Bezug auf Grammatiken finden sich auch die Bezeichnungen LR(k)-Sprache mit k>0.

Deterministisch-kontextfreie Sprachen, bei denen alle Wörter mit einem überall gleichen, ansonsten nicht vorkommenden Symbol enden, sind sogar LR(0)-Sprachen.

Die Definition geht auf Ginsburg und Greibach zurück.

• Seymour Ginsburg und Sheila Greibach, Deterministic context-free languages, Information and Control 9 (1966), 620–648
• Knuth, On the Translation of Languages from Left to Right, 5. Connections with Deterministic Languages