# context free grammar accepted and generated language problems

I'm having problems completing the following questions, I am able to attempt them but don't know if they are correct. Any help would be much appreciated.

Answer the following questions for a context free grammar $G=(N,\Sigma,P,S)$, where $N,\Sigma, P, S$ represents the set of non-terminal symbols, the set of production rules, and start symbol, respectively. Let $N=(S, A, B), \Sigma = (a,b), P= (S\rightarrow aAa|bAb, A\rightarrow aAa|bAb|B, B\rightarrow aB|bB|\epsilon)$.

$(1)$ Give a derivation of string $baabab$ in $G$

$(2)$ Give the language $L(G)$ that is generated by $G$

$(3)$ Give a context free grammar which generates the language $L(G)\cap(w \epsilon \Sigma^*| |w|_a = 2n + 1, n\geq1, where |w|_a= 2n+1, n\geq 1)$ represents the number of occurrences of $a$ in $w$.

$(1)$ $S\rightarrow bAb, A\rightarrow baAab, A\rightarrow baBab, B\rightarrow baaBab, B\rightarrow baaBbab, B\rightarrow baa\epsilon bab, \rightarrow baabab$

$(2)$ The language generated by the CFG seems to be a and b recurring to various powers eg. $aabbaaabab$. im not sure exactly what the syntax is for writing this is, but have attempted with $((a^nb^m)^*|n,m \geq 0)$

$(3)$ For this question also im not sure about the syntax for writing the language accepted by both $L(G)$ and $|w|_a=2n+1$. The way i understand it it should accept recurring a and b's like from L(G) but the a's have to be amod2=1. The following CFG seems to generate the union of these two languages.

$(S\rightarrow a^3Aa^3|bAb)$

$(A\rightarrow a^2Aa^2|bAb|B)$

$(B\rightarrow aB|bB|\epsilon)$

## 3 Answers

$\mathbf{(1)}$ Your derivation is basically correct, but your notation is not. The derivation is

$$S\Rightarrow bAb\Rightarrow baAab\Rightarrow baBab\Rightarrow baaBab\Rightarrow baabBab\Rightarrow baabab\;,$$

where the productions $S\to bAb$, $A\to aAa$, $A\to B$, $B\to aB$, $B\to bB$, and $B\to\epsilon$ have been applied in that order.

$\mathbf{(2)}$ Any derivation must start one of the productions $S\to aSa$ and $S\to bSb$: those are the only ones initially applicable. At that point you have one of the strings $aAa$ and $bAb$, so the $A$ productions are the only ones that are applicable. After you apply one, you still have a string with only one non-terminal symbol, either $A$ or $B$. If it’s $A$, you can repeat the process, but eventually you’ll have to apply $A\to B$, since the only terminal production in the grammar is $B\to\epsilon$.

What kinds of strings can we produce from $A$ before we end with an application of $A\to B$? The productions $A\to aAa$ and $A\to bAb$ ensure that the string to the left of the $A$ is always a mirror image (reversal) of the string to the right of the $A$. Thus, we can get any string of the form $w^RAw$. This means that after applying $A\to B$, we’ll have one of the two derivations:

$$S\Rightarrow aAa\Rightarrow^*aw^RAwa\Rightarrow aw^RBwa\;,$$

or

$$S\Rightarrow bAb\Rightarrow^*bw^RAwb\Rightarrow bw^RBwb\;,$$

where $w$ can be any word in $\{a,b\}^*$. In other words, at the point in the derivation just after we apply the production $A\to B$, the possible strings are precisely the strings of the form $w^RBw$ such that $|w|>0$. To complete the analysis, work out what kinds of strings $B$ can produce. If $u$ is such a string, the language must contain words of the form $w^Ruw$, where $|w|>0$.

$\mathbf{(3)}$ The language in question consists of the words in $L(G)$ with the property that the number of $a$s in the word is an odd number greater than $1$. (Since $n\ge 1$, $2n+1\ge 3$.) If $w^Ruw$ is a word in $L(G)$, clearly $|w^R|_a=|w|_a$, so the number of $a$s in $w^Rw$ is even. Thus, the grammar must ensure that the $u$ part contains an odd number of $a$s. If we begin a derivation by applying the production $S\to aAa$, the $u$ part can contain any odd number of $a$s, since we already have two of them. If, on the other hand, we begin by applying $S\to bAb$ and never apply $A\to aAa$ before finally applying $A\to B$, we must ensure that the $u$ part contains at least three $a$s.

I suggest introducing a new non-terminal $C$ and replacing the production $S\to bAb$ by $S\to bCb$. $C$ should then behave much like $A$. In particular, you’ll want $C\to bCb$. However, if $C$ ever generates a pair of $a$s, the $u$ section of the final word can contain any odd number of $a$s, so it’s as if you’d started by applying $S\to aAa$; thus, you might as well have $C\to aAa$ instead of $C\to aBa$.

When you finally reach $B$ by applying $A\to B$, you already have at least two $a$s, so you just have to figure out how to make sure that $B$ generates a string with an odd number of $a$s. HINT: Use two non-terminals instead of just $B$.

This means that you don’t want a production $C\to B$, because $C$ can only generate strings of $b$s: when you finally ‘leave’ $C$, you need to make sure that the $u$ part contains at least three $a$s (and of course that the number of $a$s is odd), not just one. This means that you’ll need yet another non-terminal, say $D$, and a production $C\to D$. Now $D$ should behave much like $B$, except that it has to generate at least three $a$s. You can use the previous HINT to make sure that you get an odd number of $a$s; to make sure that you get at least three, you’ll want another non-terminal or two.

• thank you veyr much for your detailed answer. In regards to the language of $u$ from the second question. It seems to be a string of a's and b's to varying powers since you can put a or b to replace $B$ as much as you want. Does that mean the language for $u$ is $u=((a^nb^m)^* | n,m \geq 0)$ – dmnte Jan 25 '16 at 14:13
• @dmnte: Not quite: it has to be of the form $w^Ruw$, where $|w|>0$. The first character of $w^R$ is the same as the last character of $w$, so $u$ must begin and end with the same character. However, you’re right that there can be anything at all in the middle. In fact the language is regular and is described by the regular expression $$\big(a(a+b)^*a\big)+\big(b(a+b)^*b\big)\;.$$ – Brian M. Scott Jan 26 '16 at 0:24

$$S\rightarrow aAa|bAb\\ A\rightarrow aAa|bAb|B\\ B\rightarrow aB|bB|\varepsilon$$

$(1)$ You want the word $baabab$ so $S\to bAb\to baAab\to baaBab\to baaBbab\to baabab$

$(2)$ I think that you can "split" the language into three: first part, the middle, and the last,

e.g $\overbrace{\color{red}a\color{blue}b\color{green}a}^{\text{first}}\underbrace{aababaaba}_{\text{middle}}\overbrace{\color{green}a\color{blue}b\color{red}a}^{\text{last}}$, in the middle it can be anything but in the egdes the latter in the $i$ place from the begining equals to the $i$ letter from the end