Dyck language

views updated

Dyck language A concept used in formal language theory. Let Σ be the alphabet {a1,…,an,b1,…,bn}

The Dyck language over Σ is the set of all strings that can be reduced to the empty string Λ by “cancellations” of the form aibi → Λ

For example, Σ = {(,)}

gives the Dyck language of all balanced parenthesis strings. An important theorem characterizes the context-free languages as those representable as the homomorphic image (see homomorphism) of the intersection of a Dyck language and a regular language.

More From encyclopedia.com