edited by
330 views
1 votes
1 votes

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.
edited by

1 Answer

Best answer
1 votes
1 votes

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.

 

selected by

Related questions

1 votes
1 votes
2 answers
1
aditi19 asked Mar 24, 2019
608 views
If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of $x$ is a square } \Bigr \}$ then $L$ isRegularRecursive but not context freeContext Free but not regula...