Class

Hello! I’m not sure if I’m on the right track but here is how I solved it.
1)
S -> bAb
A -> aAaa | b

2)
S -> bAb
A -> aAaa | epsilon

I think the reason why Mattia’s solution is flawed is because we need to “remember” how many a’s are there in the first set so that we can double that number in the second set.

I would appreciate it if you could critique my understanding.

Hello everyone, I think that the proposed grammars are wrong because they do not link the balanced generation of occurrences of the symbol a.
I thought of solving the exercise in this way and I hope it is correct. If there are any mistakes or if anyone has suggestions to improve my solution, I would be grateful for your help.

L1 is not REG and this can be shown by using Pumping Lemma with a string w = b a^(N) b a^(2N) b ∈ L1, where N is the P.L. constant and w = xyz, with |xy|<= N and |y|= m >= 1.
y in this case can only appear before the second occurence of b in the string (in the part "b a^N").
If y = b, then x = ε: with k = 0, in the string there isn't the first b, then w_k ∉ L1
if y contains some of the a's: with k = 0, the constraint on balancing the number of occurrences of a's is no longer satisfied and then w_k ∉ L1.
L1 is CFL \ REG and it can be generated by the following CFG:
S → bAb
A → aAaa | b

L2 is REG and it can be generated by the following RegEx: b(aaa)*b. In this language, there is no boundary symbol between the two blocks of a's, so the number of occurrences of a in a string belonging to L2 is 0 or a multiple of 3. Since with n = 0, there are zero a, with n = 2 there are three a's, with n = 4 there are six a's, and so on.

L3 is REG since it is a concatenation of two regular languages (L2) and Regular Languages are closed under concatenation.