equal number of sequence, is language regular ?

Question

L1= Set of all strings having equal number of 00 and 11.
L2= Set of all strings having equal number of 01 and 10.
(a) Both are Regular (b) Both are Context-Free
(c) L1 is regular, L2 is Context Free (d) L1 is CF, L2 is Regular

Answer 1

L1 is well known Non Regular i.e. (00)^n(11)^n. (Since there is no common character in "00" and "11" we need to keep count of both which is not possible with a finite automata as count can be infinite).

L2 is regular and its regular Expression like 0(0+1)*0 + 1(1+0)*1 + 1 + 0 +epsilon.

Comments

Why wouldn't the regular expression ((0011)+(1100))* work for L1 ?

---

@Hodor Your regex says every 00 should be followed by 11 and every 11 should be followed by 00.. But that is not the case with given language..

---

@ Hodor , we cannot have 01100 or 01010011 from your regular expression , actually your regular expression is subset of " Equal no of 00's and Equal no of 11's"

@Laser , actually 00ⁿ11ⁿ is also subset of "equal no of 00's and equal no of 11's"

similarly aⁿbⁿ , bⁿaⁿ, (ab+ba)* all are subset of language "Equal-Equal" ( that is CFL , not regular)

---

@Praveen sir : m not getting u

---

Equal no of 00 and Equal no of 11 , also contain strings such that 1100, 0101100, 001011, etc 

actually 00n11n is also subset of "equal no of 00's and equal no of 11's" , 

And Yes for sure , it is non regular .

---

@Aditya

"Set of all strings having equal number of 00 and 11"

There is no mention of order. You can't compare it with aⁿbⁿ .

---

^^ ohh.

L = { w | w belongs to (0+1)* and n(00) = n(11) }

---

Just for clarification...

The string 010 ⊂ L2 ..so are we counting '1' twice...like 01, 10

---

Sir , If we have strings like  0101100, 001011 , so then how will we make a pda for it , whenever we will see a 0 or 1 , we 

will push it  , so now when will the pop operations be performed , since here we can't keep a track of actually when we have seen 00 or 11 , since after 0 some 1 could have come ,plz give the logic for accepting it through pda.

---

@Digvijay, can yu exlpain on L2, how is it regular ?

---

Praveen Kumar B 

Regular Expression for $L=(0(0+11^{*}0)^{*} + 1(1+00^{*}1)^{*}+\epsilon )$

and this is the DFA for given language.

If you can draw a DFA for any language it means the language is regular.

---

LeenSharma can you explain me on this Regular expression?

---

can you give an example in which a common character is present and is regular?

---

For L2 , according to the given answer it accept string 0, 00 etc. But 0, 00 doesn't belongs to language L2.

Then how can we say that L2 is regular.

---

@Digvijay  we cannot generate 01101001 with your regular expression....so i think that it is not a valid regex

Answer 2

this prob is solved before .

ans will be d)

L2 can be considered as all of the stings start and with same elements (0 or 1  )

Comments

can u share the link, where it was solved previously.