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. Die Definition geht auf Seymour Ginsburg und Sheila Greibach zurück.

In Bezug auf Grammatiken findet sich auch die Bezeichnung LR(k)-Sprache: Jede LR(k)-Grammatik beschreibt eine deterministisch kontextfreie Sprache. Umgekehrt gibt es für jede deterministisch kontextfreie Sprache ${\displaystyle L}$ ein ${\displaystyle k}$, so dass ${\displaystyle L}$ eine LR(k)-Sprache ist (d. h. eine LR(k)-Grammatik hat). Tatsächlich reicht dafür in jedem Fall ${\displaystyle k=1}$, aber nicht ${\displaystyle k=0}$. Jedoch lässt sich auch jede deterministisch kontextfreie Sprache, die nicht LR(0) ist, durch Einführung einer eindeutigen Markierung für das Wortende in eine LR(0)-Sprache überführen.