0
$\begingroup$

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

$(1^*01)11$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Jan 26, 2018 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
    Commented Jan 26, 2018 at 17:23

0

Reset to default

Browse other questions tagged or ask your own question.