The Gateway to Computer Science Excellence
+6 votes

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
in Theory of Computation by Veteran (432k points)
edited by | 322 views
D is regular, this is a problem picked up straight from Sipser.

2 Answers

+5 votes
Best answer

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


by Boss (11.6k points)
edited by

Dfa could be possible for this.

Follow this link you'll understand better

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


hence D is regular.
by Junior (811 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,398 answers
105,457 users