Class Description

UCFL: Unambiguous CFL

The class of context-free languages which can be represented by grammars where each word in the language has exactly one leftmost derivation.

Strictly contains Deterministic CFL. Strictly contained in CFL.

Linked From

CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77] and indeed UCFL.

More about...


DCFL: Deterministic CFL

The class of languages accepted by deterministic pushdown automata.

Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL, contained in UCFL, and strictly contains REG. The inclusion in UCFL is also strict.

More about...