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)$
$\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.