I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd
I thought along the following lines:
$i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or all of them are odd. But designing a DFA like this will lead to a complex and big DFA. I am not sure if there is a simpler way to design a DFA for this.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
this language is an intersection of 2 regular languages: a sequence of any number of a b and c in order: a*b*c* (a 3 stage + sink DFA will handle this one), and [abc]([abc][abc])* (which a 2 state DFA)
To create the DFA for the interesection you take the cartesian product of all stages and then connect them according to the transition function. $\delta((s_1, s_2), a) = (\delta(s_1, a), \delta(s_2, a))$
So you will end up with a 6 state + sink DFA.
$s_{a0}$ : start and $\delta( s_{a0}, a) = s_{a1}$ , $\delta( s_{a0}, b) = s_{b1}$, $\delta( s_{a0}, c) = s_{c1}$
$s_{a1}$ : accepting and $\delta( s_{a1}, a) = s_{a0}$ , $\delta( s_{a1}, b) = s_{b0}$, $\delta( s_{a1}, c) = s_{c0}$
$s_{b0}$ : $\delta( s_{b0}, a) = sink$ , $\delta( s_{b0}, b) = s_{b1}$, $\delta( s_{b0}, c) = s_{c1}$
$s_{b1}$ : accepting and $\delta( s_{b1}, a) = sink$ , $\delta( s_{b1}, b) = s_{b0}$, $\delta( s_{b1}, c) = s_{c0}$
$s_{c0}$ : $\delta( s_{c0}, a) = sink$ , $\delta( s_{c0}, b) = sink$, $\delta( s_{c0}, c) = s_{c1}$
$s_{c1}$ : accepting and $\delta( s_{c1}, a) = sink$ , $\delta( s_{c1}, b) = sink$, $\delta( s_{c1}, c) = s_{c0}$
and of course $sink$ only goes to itself
