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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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