1

if we want to generate a regular language for this FA, it would be 

(1 ∪ 0(00 ∪ 11)* (01 ∪ 10)) ◦ ((00 ∪ 11) ∪ (01 ∪ 10)(00 ∪ 11)* (01 ∪ 10))*

enter image description here Let's challenge ourselves a bit by changing the FA as below My attempt solution is 0(00)*1 U 1(11)*0 ◦ ((00 ∪ 11) ∪ (01 ∪ 10)(00 ∪ 11)* (01 ∪ 10))*

Please let me know if we my attempt is correct, What if q1 and q2 are both accept state at the same time, How should you suggest combine this two regular express into one? and how would you even approach it ? please share.

enter image description here

Dmomo
  • 143

1 Answers1

1

This almost the same question as your previous question.

First, your regular expression for the first DFA is correct. Secondly, if you take $q_1$ and $q_2$ as final states, your DFA is no longer minimal and you can actually identify $q_1$ and $q_2$ on one hand and $q_0$ and $q_3$ on the other hand. It leads you to a DFA with two states $q_0$ and $q_1$: $0$ acts as the identity and $1$ permutes the two states. The final state is $q_1$ and a possible regular expression for the corresponding language is $(0 \cup 10^*1)^*1$.

J.-E. Pin
  • 40,163