• 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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 22 '16 at 6:40
  • 1
    $\begingroup$ Enumerate all strings up to some size, say ten. Look for patterns. $\endgroup$
    – Raphael
    Sep 22 '16 at 6:55
  • $\begingroup$ @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. $\endgroup$ Sep 22 '16 at 15:31
  • $\begingroup$ Also determining if the grammar itself is LL or LR $\endgroup$ 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.

  • $\begingroup$ 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)$. $\endgroup$
    – Raphael
    Sep 22 '16 at 20:13
  • $\begingroup$ @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! $\endgroup$ Sep 24 '16 at 16:44
  • $\begingroup$ @RicardoRigaroni. You're welcome. By the way, welcome to the site! $\endgroup$ Sep 24 '16 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.