Definition
Dyck Language
Let
over be the smallest set with:
, Example:
The language of well-formed bracket expressions is the one-bracket Dyck language
.
Example
Well-formed bracket expressions
The language of well-formed bracket expressions is the smallest language over a bracket alphabet such that:
is in the language, - if
is in the language, then is in the language, - if
and are in the language, then is in the language. Equivalently, it is generated by the context-free grammar
where
is the start symbol.