Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) ...

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?

(A) L is regular, but not context-free. 

(B) L is context-free, but not regular.

(C) L is Σ*.

(D) None of these.

Hint: 

<div class="tex2jax"></div>

6Comment
sumitverma's picture
Sumit Verma @sumitverma 1 Dec 2016 03:39 pm

Any word can be decomposed to meet the criteria.

rameshbabu @somethingnew 17 Jan 2017 05:54 pm

how can it be ∑* ,if number of a = number of b

sumitverma's picture
Sumit Verma @sumitverma 17 Jan 2017 06:13 pm

@somethingnew Read the below line twice :)
L := {xy | x, y ∈ Σ* , na(x) = nb(y)} 
It is na(x) and nb(y) not na(xy) or nb(xy).

rameshbabu @somethingnew 17 Jan 2017 07:16 pm

@sumitverma , letw= aab

does w ∈ L

if yes, then how would you decompose it to x and y

sumitverma's picture
Sumit Verma @sumitverma 17 Jan 2017 07:56 pm

@somethingnew
x= a 
y=ab