CODEWITHSUNDEEP
regular-languageautomatastate-machine
Hailey
Hailey

Reputation: 157

Start state for a DFA in Automata

Suppose a DFA has to be designed which accept all string over Σ={0,1}* which start and ends with same symbol(e.g-0110,10101 etc.).Is ε a acceptable string ? Which means,Is start state a final state?

Upvotes: 2

Views: 335

Answers (2)

Patrick87
Patrick87

Reputation: 28292

It depends entirely on what is meant. Human languages are vague and imprecise; that's why we invent formalisms like regular expressions in the first place.

If this is an exercise, I would ask whomever is giving you the exercise for clarification. On the surface, two interpretations seem reasonable:

  • The empty string does not start and end with different letters, so it should not be excluded
  • The empty string does not start and end with the same letter, so it should not be included

If it is an exercise and you have the original wording, you can provide a quote, but as stated, the answer is simply not clear. If homework, you could always provide two DFAs, one for each interpretation, with some discussion of the ambiguity.

If it is just a question you made up, then you will have to answer for yourself whether you want the empty string in your language.

Upvotes: 1

jagaran
jagaran

Reputation: 1

YES.

The String ε belongs to {0,1}* and its start and end symbols are not different.So it should be accepted by the DFA

Upvotes: 0

Related Questions