Overview

Dyck language


Related Overviews

 

'Dyck language' can also refer to...

 

More Like This

Show all results sharing this subject:

  • Computing

GO

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.

{a1,…,an,b1,…,bn}

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.