0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.