I have created a DFA that is composed of 4 states and also that does not accept an empty word. However before, in the answers they give a 3 state DFA that accepts it.

Why should my DFA accept an empty word if in the empty word tbelow is no 1 at the odd place which indicates that it is not in the language?


The only requirement is that any symbol at an odd position need to be 1. Tright here is no need for a details variety of symbols, and particularly not that tbelow be at least one.

You are watching: {w| every odd position of w is a 1}

Therefore, a DFA with an initial state wright here 0 leads to a rejection state and wbelow 1 leads to a 2nd state which accepts either symbol and retransforms to the start would certainly be an acceptable answer, and would certainly accept the empty string. This would certainly be a three-state machine:



I think you are puzzled why must an empty string be a part of a discussed collection.

Let"s take a look at another instance. Consider you have actually a collection of all possible strings having eextremely character equal to 0. Such strings would be 0, 00, 000, 00000, and so on What about an empty string *? It actually pertain to this set too. Empty string does not violate the meaning of the collection.

Compare this example with yours. You must examine eexceptionally odd place of the string and also if you"ll uncover anything other than 1 you need to say that it is not an facet of you set. It is not shelp anything about whether a string must have actually an odd position to be checked.


Thanks for contributing a solution to Stack Overflow!

Please be sure to answer the question. Provide details and also share your research!

But avoid

Asking for help, clarification, or responding to various other answers.Making statements based on opinion; ago them up via recommendations or individual endure.

See more: Sketch And Label The Basic Internal Anatomy Of A Cross Section Of A Leaf

To learn even more, view our tips on composing excellent answers.

Article Your Answer Discard

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

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

Need a much better explacountry of this lengthy DFA word difficulty ( CS : Formal Language & Automata course)

site design / logo © 2021 Stack Exadjust Inc; user contributions licensed under cc by-sa. rev2021.10.20.40515

Stack Overflow functions ideal via JavaScript permitted

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can save cookies on your device and discshed indevelopment in accordance through our Cookie Policy.