Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
I found the first paragrapher of your answer confusing, because all I did is exactly what the book that I was using used in others decidability cases. All the stuff about subrotine, converting to NFA and DFA was there. Anyway, when I first thought about it, I thought there would be strings of all kinds, not only ones with 111 as a substring. I also don't understand why the set of all strings is infinite, aren't they 5 symbols strings? About the other direction, my answer would be to check the regular expression itself and see if it has a 111 substring
How to be sure that $$ S\to\epsilon$$ wasn't part of the grammar before? And how could $$ S\to SS $$ break things up? I also don't understand why it is $$ S' \to S'S|\epsilon $$ necessary.