Nested Parentheses#
Info#
Full Name |
Nested Parentheses Grammar |
Version |
4.0.0 |
Class |
Context-Free |
Kind |
Hierarchical |
Example download (.txt + .md) |
|
Origin |
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#
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}\).
S -> epsilon | a S b
The nested parentheses grammar with \(\textit{types} = \{(a, b)\}\) and \(\textit{eps} = \textit{False}\).
S -> a b | a S b