I have the following alphat {0,1}.

I'm told to draw a DFA which fulfills the following: {w|w starts with 1 and ends in 0}

This is the DFA I came up with.



This dfa is incorrect. To start, a dfa MUST define a transition for every node, including accepting nodes.

Anyhow, the current dfa would have accepted the language L = { w | w is a series of 1's and a single 0 at the end }

To correct this, you need to add another transition from B to A when it recieves 1 and a transition from B to itself when recieving 0. This is required to allow strings with 0 in the middle to also be accepted


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.