Dyck

Info

Full Name	Dyck Grammar
Version	4.0.0
Class	Context-Free
Kind	Hierarchical
Example download (.txt + .md)	.tar.gz
Origin	link

Grammar Parameters

Parameter	Description
\(\textit{types}\)	List of pairs \((\textit{op}_i, \textit{cp}_i)\) with opening and closing parentheses for each type
\(\textit{eps}\)	\(\textit{True}\) if empty string is in the language and \(\textit{False}\) otherwise

Grammar Template

\[\begin{split}S \, &\rightarrow \, \varepsilon \, \qquad \qquad &\textit{if } \textit{eps} = \textit{True} \, \\ S \, &\rightarrow \, \textit{op}_i \, \textit{cp}_i \qquad \qquad &\textit{if } \textit{eps} = \textit{False} \, \\ S \, &\rightarrow \, \textit{op}_i \, S \, \textit{cp}_i \, S \, &\\ &\forall \, (\textit{op}_i, \textit{cp}_i) \, \in \, \textit{types} \, &\\\end{split}\]

Description

Dyck grammars generate Dyck languages of the balanced strings with parentheses of \(|\textit{types}|\) types. For example, such a grammar with \(\textit{types} = \{(a, b)\}\) and \(\textit{eps} = \textit{True}\) generates the language \(\{\varepsilon, a b, ab ab, aabb, \ldots\}\).

Example Grammars

The Dyck grammar with \(\textit{types} = \{(a, b)\}\) and \(\textit{eps} = \textit{True}\).

\[\begin{split}S \, \rightarrow \, \varepsilon \, \mid \, a \, S \, b \, S \, \\\end{split}\]

Pyformlang CFG:

S -> epsilon | a S b S

---

The Dyck grammar with \(\textit{types} = \{(a, b)\}\) and \(\textit{eps} = \textit{False}\).

\[\begin{split}S \, \rightarrow \, a \, b \, \mid \, a \, S \, b \, S \, \\\end{split}\]

Pyformlang CFG:

S -> a b | a S b S

---