edited by
1,853 views
16 votes
16 votes
Construct a deterministic finite automaton accepting the following language: $\{w \in \{0, 1\}^*: w \text{ has an equal number of 01’s and 10’s }\}$. For example, $101$ is in the language because it contains one instance of $10$ and one instance of $01$ as well.
edited by

2 Answers

Best answer
29 votes
29 votes

The DFA for the given $L$ is as below. 

edited by
5 votes
5 votes
You can easily solve this by observing the fact that,a binary strings has exactly as many "01" sub-strings as "10" sub-strings iff it starts & ends with the same character

so Regex for language will be ,
L= 1(1+0)*1 + 0(1+0)*0

if  you construct DFA using this expression then it will be same as shown in answer by @srestha

Related questions

8 votes
8 votes
5 answers
1
go_editor asked May 31, 2016
1,868 views
Consider the following statement:$\text{ For all languages }L \subseteq \{0, 1\}^*, \text{ if }L^* \text{ is regular then L is regular.}$Is the above statement true? Just...
1 votes
1 votes
1 answer
3
go_editor asked May 31, 2016
635 views
Consider a uniprocessor system with four processes having the following arrival and burst times:$$\begin{array}{|c|c|c|l|} \hline&\text{Arrival Time}&\text{CPU Burst Time...