The Gateway to Computer Science Excellence
+6 votes
322 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
in Theory of Computation by Veteran (432k points)
edited by | 322 views
+2
D is regular, this is a problem picked up straight from Sipser.
+2

2 Answers

+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

by Boss (11.6k points)
edited by
0

Dfa could be possible for this.

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

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

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

hence D is regular.
by Junior (811 points)
Answer:

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
198,613 comments
105,457 users