623 views
2 votes
2 votes

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$?

  1. $L$ is regular, but not context-free
  2. $L$ is context-free, but not regular
  3. $L$ is $\Sigma^*$
  4. None of these

2 Answers

0 votes
0 votes
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
edited by

Related questions