How to turn this expression into an NFA?

Question

{$ 1^ $| is a natural number which is a multiple of 4}

This is from my Intro to Theory of Computation book. It is asking me to turn this into an NFA. I was comfortable with doing so with binary numbers but the notation natural number made me confused here. If n could be all natural numbers multiple of 4, then isn't it that there is an infinite amount of possible numbers? Is it that the alphabet here is infinite? Doesn't that make it impossible to convert this expression into an NFA?

I am actually not sure if even I'm thinking correctly about the question. So I would be really grateful if you helped me out with a clear explanation on how to approach this.

Answer 1

The alphabet is simply $\lbrace 1 \rbrace$ (there's just one symbol in it). Your NFA is supposed to accept exactly those strings over this alphabet whose length is a multiple of $4\!\text{}:$

$$\varepsilon, 1111, 11111111, 111111111111, \dots$$

(where $\varepsilon$ denotes the empty string).

So the language the NFA should accept is infinite, but the alphabet is not.

By the way, I'm assuming here that your book considers $0$ to be a natural number. (If, on the other hand, it uses the phrase "natural number" to mean "positive integer", then the NFA shouldn't accept the empty string.)

Answer 2

The language you want to recognise is defined by the regular expression (1111)*. The usual algorithms for generating automata that recognise languages defined by regular expressions will then give you what you want.