edited by
1,984 views
9 votes
9 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
edited by

2 Answers

Best answer
13 votes
13 votes

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

1 votes
1 votes
We can also write the regular  expression as :

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

hence D is regular.
Answer:

Related questions

3 votes
3 votes
1 answer
1
4 votes
4 votes
2 answers
4
Arjun asked Dec 18, 2018
4,149 views
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits ?$0.1$$0.2$$0.4$$0.5$All the above