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.

  • $\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