Dyck language

Quick Reference

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.


aibi ↑ Λ

Σ = {(,)}

Subjects: Computing.

Reference entries