[Math] Let G be the language of all string over {0,1} that do not contain a pair of 1s that are separated by a odd number of symbols.

automatacomputer scienceregular expressionsregular-language

This is a questions in book, Introduction-To-The-Theory-Of-Computation-Michael-Sipse, Third edition, P85. This is not hw problem(solution is given)
So based on the given hit, we negate it first as
F'={w|w contains a pair of 1s that are separated by an odd number of symbols} over {0,1}. and given solution draw the NFA below.

enter image description here

My question is,
what does it mean by "a odd number of symbols"?

is the given graph graph correct, (I don't think so, since it doesn't have any accept states)

Best Answer

By "a pair of 1s separated by an odd number of symbols", it means two 1s with an odd number of symbols ({0, 1}) between them.

E.g.: 111 has three pairs of 1s. The one formed by the first and the last 1 (111) is separated by an odd number of symbols (1). The other two, formed by the first and the middle one (111), and the middle one and the last (111) are NOT separated by an odd number of symbols, since they have 0 symbols between one another.

The state diagram you provided is, indeed, missing an accept state, which should be q3.

Related Question