Dyck language

Related Overviews


'Dyck language' can also refer to...


More Like This

Show all results sharing this subject:

  • Computing


Show Summary Details

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

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.