Cheap and Secure Web Hosting Provider : See Now

[Answers] Describing the language formed by a particular grammar

, ,
Problem Detail:
• 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.

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.

Question Source : http://cs.stackexchange.com/questions/63760

3.2K people like this