This question already has an answer here:

Right now I am trying to learn how to work with automata and regular grammar, and I encountered the following exercise:


I found the following solution, but I am not really sure if it's right.

enter image description here

What I didn't understand it's from where exactly I should continue after I close the parenthesis or start a new one (let's say the expression was $11(1^*01)$ . When I start the parenthesis and I have A ->1B -> 1C, do I continue the automata after the C or I return to A?

Thank you.


marked as duplicate by David Richerby, Evil, D.W. Jan 26 '18 at 20:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You'd continue the automaton.However, in this example, you don't need the parentheses at all. Could you find the FA corresponding to $1^*0111$? That's the same expression as the one in your post. You'd need parens for something like $(10)^*$ or $01(1+01)$. $\endgroup$ – Rick Decker Jan 26 '18 at 14:55
  • $\begingroup$ To check whether it's right, try to either find a string that one accepts and the other rejects. If you can't do that, try to prove that no such string exists. If you can't do that, try harder to find one. If you still can't do that, use what you've learnt to try harder to prove there's no string. And so on until you're done. $\endgroup$ – David Richerby Jan 26 '18 at 17:23