# Describing the language formed by a particular grammar

• G → G B ⏐ G N ⏐ ε
• B → ( E )
• E → E ( E ) ⏐ ε
• N → ( L ]
• L → L E ⏐ L (⏐ ε

For this grammar, the prompt asks to describe in the language that this grammar describes and builds.

I got to the point of first trying at defining the language each one builds but the recursiveness of this grammar threw me off a bit.

I'm kind of stuck, thus far I tried to start with let's say N and try to describe it as generating a left paren followed by a left paren and right bracket.

I could really use some direction on where to go with this.

• Welcome to CS.SE! Have you searched this site to look for similar questions that might be helpful? In particular, please make sure to read cs.stackexchange.com/q/50456/755 and cs.stackexchange.com/q/10605/755 and cs.stackexchange.com/q/60109/755. – D.W. Sep 22 '16 at 6:40
• Enumerate all strings up to some size, say ten. Look for patterns. – Raphael Sep 22 '16 at 6:55
• @Raphael Just saw your comment! Think I got it in terms of thinking how the strings are formed. Now just thinking about how to create the parse tree for the right derivation of the string ((]() I got the tree for the left, probably crawl around and look for more resources. – Ricardo Rigaroni Sep 22 '16 at 15:31
• Also determining if the grammar itself is LL or LR – Ricardo Rigaroni Sep 22 '16 at 15:33

There doesn't appear to be a simple description for the language generated by this grammar, but here's what happens.

1. From $E$ we have the productions $E\rightarrow E(E)\mid\epsilon$. The first few strings generated from $E$ are: \begin{align} \epsilon &\quad E\Rightarrow\epsilon\\ (\:) &\quad E\Rightarrow E(E)\stackrel{*}{\Rightarrow}(\:)\\ (\:)(\:) &\quad E\Rightarrow E(E)\Rightarrow E(E)(E)\stackrel{*}{\Rightarrow}(\:)(\:)\\ (\:(\:)\:) &\quad E\Rightarrow E(E)\Rightarrow E(E(E))\stackrel{*}{\Rightarrow}(\:(\:)\:) \end{align} It's not too hard to show inductively that $E$ generates all and only the strings of balanced parentheses, i.e., the strings over $\{(\;,\, )\}$ that could appear in a legal arithmetic expression. Let $\mathcal{B}$ denote this language.
2. From the production $B\rightarrow (E)$ we see that $B\stackrel{*}{\Rightarrow}(\mathcal{B})$, namely any string of balanced parentheses enclosed in $(\,)$.
3. From the productions $L\rightarrow LE\mid L\:(\:\mid\epsilon$. It's not too hard to see that $L$ generates all strings over $\{E,\,\,(\,\}$. Call this language $\mathcal{L}$. In simple terms, $L$ generates all strings of balanced parentheses interleaved with an arbitrary number of left parens.
4. From $N\rightarrow\,(\,L\,]$ we see that, similarly to step (2), we have $N\stackrel{*}{\Rightarrow}(\,\mathcal{L}\,]$
5. Finally, it's not too hard to see that from the productions $G\rightarrow GB\mid GN\mid\epsilon$, that $G$ generates all strings over $\{B,N\}$, so we have that the language of this grammar will generate all strings made from the concatenation of terms of the form $(\mathcal{B})$ and $\:(\mathcal{L}\:]$ in any order.

For example, a string generated by the grammar is $((\:)(\:)((\:]\,(((\:)(\:)))$, where I've separated the $N$ and $B$ substrings for clarity.

As I said at the start, not pretty.

• This approach can be used to derive a specification for the language that is simpler, at least. For instance, $\mathcal{G} = \mathrm{SEQ}\bigl( \mathtt{(}\mathcal{B}\mathtt{)} \cup \mathtt{(}\mathrm{SEQ}(\mathcal{B} \cup \{\mathtt{(}\})\mathtt{]} \bigr)$. – Raphael Sep 22 '16 at 20:13
• @Rick Decker thank you so much! Our professor went over class the other day and it started to click but the way you explained it makes more intuitive sense and a lot clearer than she explained in class. I got some learning to do! – Ricardo Rigaroni Sep 24 '16 at 16:44
• @RicardoRigaroni. You're welcome. By the way, welcome to the site! – Rick Decker Sep 24 '16 at 17:20