Virtual Gate Test Series: Theory Of Computation - Languages

Question

Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language:

L := {xy | x, y ∈ Σ* , na(x) = nb(y)}
What can we say about L?

1. L is regular, but not context-free.
2. L is context-free, but not regular.
3. L is Σ*.
4. None of these.

Answer 1

See its saying that number of a's in x should be equal to number b's in y. So it will represent the $\sum $*.

Because every string comparable with any one. like X is having $\epsilon$ then Y can have any number of a's and if there is one a in X then you can generate Y with one b and any numbers of a's in Y and if there is two a's in X then you can generate Y with 2 b's & any number of a's in Y. So like wise every string can be generated.

So Option C.