TIFR CSE 2019 | Part B | Question: 10

Question

Let the language $D$ be defined in the binary alphabet $\{0,1\}$ as follows:

$D:= \{ w \in \{0,1\}^* \mid  \text{ substrings 01 and 10 occur an equal number of times in w} \}$

For example , $101 \in D$ while $1010 \notin D$. Which of the following must be TRUE of the language $D$ ?

• A. $D$ is regular
• B. $D$ is context-free but not regular
• C. $D$ is decidable but not context-free
• D. $D$ is decidable but not in NP
• E. $D$ is undecidable

Comments

D is regular, this is a problem picked up straight from Sipser.

---

similar one- https://gateoverflow.in/47443/isi2014-cs-4a

Answer 1

Regular expression for the language D$=0(0+1)^*0+1(0+1)^*1$

DFA: http://flolac.iis.sinica.edu.tw/flolac11/lib/exe/logic_computation_theory_hw2s.pdf

Comments

Dfa could be possible for this.

Follow this link you'll understand better https://gateoverflow.in/47443/isi2014-cs-4a

---

Regular expression should include $\in, 0, 1$ as well

Answer 2

We can also write the regular  expression as :

(1*100*11*)*+(0*011*00*)*

hence D is regular.