Nested Parentheses

Info

Full Name	Nested Parentheses Grammar
Class	Context-Free
Kind	Hierarchical
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 \, &\\ &\forall \, (\textit{op}_i, \textit{cp}_i) \, \in \, \textit{types} \, &\\\end{split}\]

Grammar Description

Nested parentheses grammars generate languages of the nested parentheses of \(|\textit{types}|\) types. For example, such a grammar with \(\textit{types} = \{(a, b)\}\) and \(\textit{eps} = \textit{True}\) generates the language \(\{a^n b^n \ | \ n \geq 0\}\).

Example Grammars

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

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

Pyformlang CFG:

S -> epsilon | a S b

---

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

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

Pyformlang CFG:

S -> a b | a S b

Recursive State Machine

start: S
[box S]
start: 0
final: 2
0 --type_r--> 1
1 --type--> 2
0 --subClassOf_r--> 3
3 --subClassOf--> 2
3 --S--> 5
5 --subClassOf--> 2
1 --S--> 4
4 --type--> 2