Dyck language
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.
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
You Might Also Like
NEARBY TERMS
Dyck language