0
$\begingroup$

I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.

The alphabet is $\Sigma=\{0, 1\}$ and the language is: $$L = \{x \in \Sigma^*\mid \#_0(x)>\#_1(x)\text{ and }\#_1(x)\leq3\}\,,$$ where $\#_i0(x)$ means the number of $i$s in $x$.

When I should send it to a dead/trap state and what should the DFA look like?

$\endgroup$
1
$\begingroup$

As with any automaton, the states need to encode all the information you need to decide whether or not to accept the string you've read so far. In this case, that means that number of $0$s and $1$s that you've seen. Except you can't quite do that, because that would require infinitely many states. However, if you look more closely at the definition of the language, you'll see that you don't need to know the exact number of $0$s and $1$s: for example, if you've seen six $1$s, that's the same as seeing seven, or a million.

Once you've worked out what the states are, work out what the transitions between them are. You'll find that you have a trap state, without needing to figure out what it should have been. Trap states occur "naturally", whenever you've seen enough of the input to be able to say, "I don't care what else I see: I'm rejecting this string!"

$\endgroup$

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.