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

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

- $D$ is regular
- $D$ is context-free but not regular
- $D$ is decidable but not context-free
- $D$ is decidable but not in NP
- $D$ is undecidable

+5 votes

Best answer

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

0

Dfa could be possible for this.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,398 answers

198,613 comments

105,457 users