Skip to main content
user2752471's user avatar
user2752471's user avatar
user2752471's user avatar
user2752471
  • Member for 10 years, 11 months
  • Last seen more than 1 year ago
awarded
awarded
awarded
awarded
Loading…
comment
Decidability of an regular expression
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
comment
Kleene star closure of a context free grammar
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.
awarded
asked
Loading…
awarded
asked
Loading…
revised
Decidability of an regular expression
added 210 characters in body
Loading…
asked
Loading…