Isi Kolkata 2022

Question

Prove or disprove the following statements:
(i) L1 = {0^i1^j | i, j ∈ N} is a regular language.
(ii) L2 = {0^n1^n | n ∈ N} is a regular language.
(iii) For x ∈ {0, 1}*,
• R(x) denotes the string obtained by reversing the
string x.
• C(x) denotes the string obtained by flipping 0 to 1 and 1 to 0 in the string x.
L3 = {x ∈ {0, 1}* | x = R (C (x))} is a regular language.

How to solve this in subjective way..

Comments

For the first one draw the dfa...or give regular expression which one easy for you to proof it is regular.

For the second one you can use pumping lemma for regular language or myhill nerode theorem to show infinite states are there.

---

3. L3 = {x ∈ {0, 1}* | x = R (C (x))} is a regular language bcz it covers all length string if you expand it you will get some pattern which is repeating in all length of string like for 2 length string 00 take care of  11 belong to L and 11 will take care 00 belong to L similarly 01 and 10 so there exist pairs of string in each length of strings on which performing operation x = R (C (x)) wil take care of each other Hence It contain all length of string so, Regexp. is (0+1)* therefore it is regular

---

For proving (ii) non-regular using Myhill-Nerode Theorem
Let $L = \{0^n 1^n | n \in N\}$
We have distinguishing set $S = \{0^i | i\geq1\}$

Take any two strings from $S$, let $x = 0^m$ and $y = 0^n$ and take $z = 1^m$

So, $xz = 0^m 1^m \in L$ but $yz = 0^n 1^m \notin L$, so all pairs of S are distinguishable to L.

Hence there are infinite many equivalence classes so $L$ is non-regular.

---

Iii)

x=R(C(x))

Take x=00

C(x)=11 now reverse of c(x)=11

So x =! R(c(x))

But in case 01

C(x)=10 now reverse of c(x)=01

So for this  case x=R(C(x))

Now in case of 11 its false and 10 its true...Language is like={01,10,0101,1010,......}

This is regular.we can easily create dfa for this...

 

Can anyone confirm me is it right or wrong?