My textbook has a problem -
Find NFA of language $1^*(001^*)^*$.
I have following question-
Suppose A is a language with regular expression $(001^*)^*$. Then will each occurrence of the expression within brackets has to be same? In other word, will $00100$ be accepted by A? (here first occurrence of $001^*$ is $001$, and second occurrence of $001^*$ is $00$).
Your language consists of all the words of the form $1^{n_0}001^{n_1} 001^{n_2}\dotsm 001^{n_k}$, where $n_0, n_1, \ldots, n_k$ are non-negative integers (possibly equal to $0$) and $k \geqslant 0$.
Hint. Show that your language is actually equal to $(00 + 1)^*$. Then prove it is accepted by an (incomplete) two-state deterministic automaton.