I have got these Context-free grammar/regular expression:
(1) $abba^{*}$
(2) $abb(a+b)^{*}$
(3) $a^{*}ba^{*}ba^{*}$
(4) $S \implies abA \\ A \implies Aa|b$
(5) $S \implies aS|bA \\ A \implies aA|bB \\ B \implies aB|\varepsilon$
(6) $S \implies SA|\varepsilon \\ A \implies abba$
Note: $\varepsilon$ present empty word ("")
And these languages:
(A) $\{a, b\}^{*}$
(B) $\{w \in \{a, b\}^{*} | \text{w start with prefix abb} \}$
(C) $\{ abba \}^{*}$
(D) $\{w \in \{a, b\}^{*} | \text{number of b in word is equal to 2} \}$
Which languages are generated by Context-free grammar/regular expression above?
My result:
$ (1) - B - D \\ (2) - B - D \\ (3) - - - D \\ (4) - - - D \\ (5) - - - D \\ (6) A - C - $
Please can somebody check it?
The regular expression $abba^*$ matches the strings $abb,abba,abbaa,\ldots$, i.e., all strings that start with $abb$ and then have any number of $a$s (including none at all).
In other words, $abba^*$ does not generate any of the four languages.
The regular expression $abb(a+b)^*$, on the other hand, exactly matches $(B)$: every $w\in\{a,b\}^*$ that starts with $abb$ matches $abb(a+b)^*$, and every every word that matches $abb(a+b)^*$ starts with $abb$. It does not match $(D)$, however: $bb$ is in $(D)$ but does not match $abb(a+b)^*$.
You are correct about the regular expression $a^*ba^*ba^*$: it does indeed match language $(D)$ and none of the other three.
Let’s take a look at what the grammar in $(4)$ generates. You can apply the first production only once, and you must begin with it, so every derivation starts $S\Rightarrow abA$. Now you can apply the production $A\to Aa$ $n$ times for some $n\ge 0$, but eventually you must apply $A\to b$ in order to get a terminal word. Thus, every derivation looks like this:
$$S\Rightarrow abA\Rightarrow^n aba^nA\Rightarrow aba^nb\;.$$
The language of this grammar is $\{aba^nb:n\ge 0\}$. This is a subset of languages $(A)$ and $(D)$, but it’s not equal to either of them. For instance, $bb$ is in both $(A)$ and $(D)$, but it’s not in this language.
The grammar in $(5)$ is a bit more complicated, but it’s still not too hard to analyze. Any derivation must begin with some number of applications of $S\to aS$, followed by an application of $S\to bA$; at this point it looks like
$$S\Rightarrow^m a^mS\Rightarrow a^mbA$$
for some $m\ge 0$. We can now apply $A\to aA$ some number of times — say $n$ times — but eventually we must apply $A\to bB$, since the only way to terminate the derivation is to get a $B$. We now have
$$S\Rightarrow^m a^mS\Rightarrow a^mbA\Rightarrow^n a^mba^nA\Rightarrow a^mba^nbB$$
for some $m,n\ge 0$. We can now apply $B\to aB$ some number of times, say $\ell$, and then finally $B\to\epsilon$ to get the derivation
$$S\Rightarrow^m a^mS\Rightarrow a^mbA\Rightarrow^n a^mba^nA\Rightarrow a^mba^nbB\Rightarrow^\ell a^mba^nba^\ell B\Rightarrow a^mba^nba^\ell$$
for some $m,n,\ell\ge 0$. This is exactly the language generated by the regular expression $a^*ba^*ba^*$, so you’re correct in saying that it matches $(D)$ and nothing else.
Finally, the grammar in $(6)$ allows $m$ applications of $S\to SA$ for any $m\ge 0$, but eventually we must apply $S\to\epsilon$. Thus, we can get the derivations
$$S\Rightarrow^mSA^m\Rightarrow A^m$$
for each $m\ge 0$. Each $A$ will then turn into the terminal string $abba$, and we’ll get $(abba)^m$ for any $m\ge 0$. (Note that it doesn’t really matter when we apply $A\to abba$: I chose to do it only after getting rid of the $S$, but you can mix applications of $S\to SA$ and $A\to abba$ without affecting the final result.) The language $\{(abba)^m:m\ge 0\}$ is exactly the $\{abba\}^*$, i.e., $(C)$. It is not language $(A)$, however, since $(A)$ includes every possible finite string of $a$s and $b$s, and this language clearly does not: it does not include $b$, for instance.