Regular Languages

Question

if this is regular and its Regular expression can be written as [(0+1)^*0(0+1)*0]+ [(0+1)^*1(0+1)*1] then it will also include those strings where first W₂ second W₂ are different. I am not getting this somebody please clear this doubt.

Comments

i think its recursive....string matching can be done by TM.

---

This is regular for sure.

---

it can be regular ...if {1,0}^*   instead of {1,0}⁺

---

w1 w2 w3 all are independent but there in one string matching of w2 with itself so it should be done by LBA so its CSL language hence recursive d) option.

---

@Prerna $L$ is a set first of all- as long as the condition for being an element is satisfied, a string becomes element of $L$. i.e., we just need one path for a string to be in $L$- and we never look for one path to remove a string from $L$.

---

won't it include all other strings which aren't a part of this language?

---

No - you can try to get one.

---

okay i get it for this one.

but what about L={wxyw∣x,y,w∈(a+b)+}  why do we say this isn't regular? we can do the same thing for this one also, we can assume w to be a or b?

---

Simple reason - we cannot write a regular expression for it. $L$ does include string of the form starting and ending with same letter and having at least four letters. But it also has strings of the form,

$00111001, 000011100001, 0001000001 \dots$ where we need a power to ensure the first part matches exactly like the last part.

---

okay so even if we  make x and y to eat up the entire middle part leaving last two characters we can have 0 in the beginning and 1 in the end therefore we can't write RE for this? am i getting it right?

---

yes, some strings (infinite of them) cannot be captured by a regular expression.

Answer 1

RE = (0 + 1)⁺ 0  (0 + 1)⁺ 0  +   (0 + 1)⁺ 1  (0 + 1)⁺ 1

here w₂ is either 0  or 1. It can be any other string also, but in all such strings this condition also gets satisfied as a string can start with either 0 or 1 only.

Comments

your RE generates 0001, which is not in $L$.

---

@arjun sir is there any flaw in my answer .if it is wrong than correct it .plz .thanks .

---

it is not correct. Answer is given in question only.

---

answer is corrected

Answer 2

w1 w2 w3 all are independent but there in one string matching of w2 with itself so it should be done by LBA so its CSL language hence recursive

d) option answer .