Language of a grammar vs regular expression vs nfa

Question

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the language of this figures (nfa, regular expression and grammar):

Answer 1

Note that $(a \mid b)^{*}$ means $\{\varepsilon, a, b, aa, bb, ab, ba, \dots \}$, so $(bb \mid b)^{*} = \{\varepsilon, b, bb, bbb, \dots \} = b^{*}$. That leads to

$$R = (a \mid b) (bb \mid b)^{*} = (a \mid b) b^{*}$$

So the language created by $R$ is $L(R) = \{ a^lb^k \mid k \in \mathbb{N}_0, 0 \leq l \leq 1\}$.

Converting your NFA to an equivalent DFA we get

Now we can see that $M$ accepts all words of the type $xy$ where $x$ can either be $a$ or $b$ (but not nothing), and $y = b^{*}$ (including $y = \varepsilon$). That means $L(R) = L(M)$.

Finally, let's take a look at $G$:

\begin{align*} S &\rightarrow aAB \mid bAb \\ A &\rightarrow bbA \mid b \mid \varepsilon \\ B &\rightarrow bB \mid bAB \mid \varepsilon \end{align*}

Case 1: $S \rightarrow aAB$: We can derive the $A$-part with either nothing, one $b$ or as much $b$'s as we like. We can derive the $B$-part with either nothing, as many $b$'s as we like or go the $A$-part.

Case 2: $S\rightarrow bAb$: In the $A$-part we can derive nothing, one $b$, or as many $b$'s as we like. This, how you pointed out, leads to the fact the the word $b$ wouldn't be accepted.

So $G$ is equivalent to:

\begin{align*} S &\rightarrow aT \mid bTb \\ T &\rightarrow bT \mid \varepsilon \end{align*}

which leads to $L(G) = \{a^l b^kb \mid k \in \mathbb{N}, 0 \leq l \leq 1\} \neq L(M) = L(R)$.

Answer 2

The regular expression tells us that the language accepted is either an 'a' and then any number of 'b's or a non-zero number of 'b's. It's not hard to see that any such string will be accepted by the NFA (after 'ab' or a single 'a' we have states 2 and 3 active in the NFA and then the bs just cycle them around.) Additionally, the empty string isn't accepted. After the first letter we can never again be in state 1, and no other state has an outgoing 'a' edge. This checks out.

As for the CFG: 'A' can clearly become any number of 'b's. It is the smallest set containing 0, 1 and 2 + any number it contains. B can similarly be any number of 'b's. But, it seems you are right. S can become 'a' followed by any number of 'b's or 2 + any number of 'b's. We want only one 'b' to be required. Perhaps this is a typo?