CMI2014-A-05

Question

Let $\Sigma = \{a, b\}$. For a word $w \: \: \in \Sigma^*$ let $n_a(x)$ denote the number of $a$'s in $w$ and let $n_b(x)$ denote the number of $b$'s in $w$. Consider the following language:

$L:=\{ xy \mid x, \: y \in  \Sigma^*, \: \: n_a(x) = n_b(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 $\Sigma^*$
• D. None of these

Answer 1

Answer B)

As here number of a's in x= number of b's in y

Now, x could be aaabb

y could be bbb

it satisfying condition

So, it is a NCFL

Comments

It should be C only.

https://gateoverflow.in/29610/regular-non-regular-language

---

yes number of b in x , and number of a in y could be different

example bbb could be a string with only b in x

bbaaa - bb is part that b in x and aaa is part that a in y

bbabbb - here say bbabb in x and b in y [here we have to maintain a restriction, we cannot take any thing as x and anything as y]

b³ aⁿ b^n-1 - here b³a^n-1 in x part and ab^n-1 in y part. right?

though it is not making any problem in final string getting (a+b)^*

---

Thanks for the answer but I can't understand properly please explain it more clear that help me alot.

---

see link of @Praveen Sir

---

Its okay with your answer with proper explanation and I understand it clearly.

Thanks a lot.

---

Answer should be $(C)$ and it’s language is $\sum^*$ .

Answer 2