321 views

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$ ?

1. $D$ is regular
2. $D$ is context-free but not regular
3. $D$ is decidable but not context-free
4. $D$ is decidable but not in NP
5. $D$ is undecidable

edited | 321 views
+2
D is regular, this is a problem picked up straight from Sipser.
+2

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

by Boss (11.6k points)
edited
0

Dfa could be possible for this.

+1 vote
We can also write the regular  expression as :

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

hence D is regular.
by Junior (787 points)