So i need to draw a DFA for this language, i know i need to separate for 2 DFAs and than combine them both.
What is the approach ? How do i do the $\Sigma^*$ inside the DFA ? The 0100 condition is kinda easy, also the 11 language.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
How to draw $\{w|w≠\Sigma^*11\Sigma^*\}$:
Three states $S_0, S_1, S_2$ are needed. $S_0$ is both a initial state and an accepted state, $S_1$ is an accepted state. Whenever you read a $1$, go from $S_i$ to $S_{i+1}$. Finally let $S_2$ be the dead state.
Similarly you can draw the $\{w|w=\Sigma^* 0100\}$.
In the end, we combine these two DFAs with a cartesian product. You can look up here: https://stackoverflow.com/questions/7780521/how-to-use-the-intersection-construction-to-form-a-dfa
