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.

Question

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.

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)

Answer 1

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.

Answer 2

Actually I doubt about the graph provided as it accepts number of 1s more than 2. Mathematically (please correct me if I am wrong) for the given language np string may have more than 2 1s. Because in any combination of 1s in a string which has more than 2, let say 3 1s than at least 1 pair of this 1s will be separated by odd number of symbols. Here is the proof: let say positions of 3 consecutive 1s in a string are n,m and k in increasing order. Number of symbols are m-n-1, k-m-1 and k-n-1. if m-n-1 and k-m-1 are odd (both) or even, then k-n-1 is odd. And if any of m-n-1 and k-m-1 is odd (but not as in upper case both) then we already have 2 1s which are separated by odd number of symbols. So we cannot have more than two 1s in string for given language.