Dyck Language

Definition

Dyck Language

Let $D_{n}$ over $Γ_{n} = {(_{1},)_{1}, \dots, (_{n},)_{n}}$ be the smallest set with:

$ε \in D_{n}$

$v \in D_{n} ⟹ (_{i} v)_{i} \in D_{n}$ , $1 \leq i \leq n$

$v_{1}, v_{2} \in D_{n} ⟹ v_{1} v_{2} \in D_{n}$

Example: $D_{2} = {(,), [,]}$

The language of well-formed bracket expressions is the one-bracket Dyck language $D_{1}$ .

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 $w$ is in the language, then $(w)$ is in the language,

if $w_{1}$ and $w_{2}$ are in the language, then $w_{1} w_{2}$ is in the language.

Equivalently, it is generated by the context-free grammar
$G = ({A}, {(,)}, {A \to ε ∣ (A) ∣ AA}, A)$
where $A$ is the start symbol.

Lukas' Notes

Dyck Language

Definition

Example

Graph View

Table of Contents

Backlinks