Let $\Sigma=\{a,b,c\}$. Construct a minimal DFA recognizing the language constructed by the regular expression

87 Views Asked by At

Let $\Sigma=\{a,b,c\}$. Construct a minimal DFA recognizing the language constructed by the regular expression :

$$b ∘ a ∘ (a, b)\text{*} ∘\ ( (a ∘ c) ∩ (b, c)\text{*} )\text{*} ∘\ c $$

where $∘$ means concatenation

What is the best approach to constructing a minimal DFA in this case?

1

There are 1 best solutions below

0
On

HINT: $(a\circ c)\cap(b,c)^*$ is empty, so the given regular expression is equivalent to the much simpler one $b\circ a\circ(a,b)^*\circ c$, for which you should not have much trouble designing a DFA. Once you have one, you can use standard techniques to convert it to a minimum DFA for the language, though you may well come up with a minimal DFA right off the bat.