hello
in exam 2021- February
exercise 1
- can some explain please why there is ε in the arc between q0 and q2 and between q3 and q2 in the first reduced automata
- for The second automaton, how the arc are constructed?
Hello Khaled,
let me try to provide you a possible solution showing all the steps of algorithm in details, following the method explained in the textbook, section 3.2.2. You can find it in the images below (I hope my handwriting is understendable properly).
I think the crucial passage is in the label 1+00*1 for arc q0q2, you can write it as (ε+00*)1 (similar for arc q3q2), which is exactly what we have in the solution.
About point b), I didn't write it on paper with good handwriting, but the elimination of q3 follows the same steps. Maybe the "trap" is in the state q0: this state is predecessor of q3, but also a successor, so the arc R11 is the arc from q0 to q0... which is the loop. And the arc from q0 to q2, 1+0(ε+0*+10*)1 is, again, another mode to take some common factors outside parentheses, I think it is not an error if you keep the expression explicit.
Let me know if you need the details for that step too.
Thanks a lot Marco for your time and sharing such explanation
I got the idea
I got the idea
I found similar exercise in Jan-2019 but I am not sure how can I proceed, I did the following in the below image,
if you solved it please share it with me
thanks in advance
This method is almost correct (of course you have to remember that the final regular expression E is the union of E1 and E2), but there is something to adjust, if I remember properly: when you use the state elimination in more than one final state, when you remove one of them and keep the others you have to continue with state elimination method. For example, in the first automaton you eliminated q3 and keep q2, but before drawing initial->final states you need to calculate the arcs labels considering predecessors and successors as above. In this case they are both q0, R is its loop 1, Q=01, P=1, S=0 and so on.
At the end of this procedure, the arcs from q0 to q2 and viceversa are the same as you write correctly (I don't understand if the arc from q2 to q0 has + operator, remember that "0,1" means "0 OR 1" whichs is "0+1"), but the loop in q0 is quite more complex, 1+010*1
At the end of this procedure, the arcs from q0 to q2 and viceversa are the same as you write correctly (I don't understand if the arc from q2 to q0 has + operator, remember that "0,1" means "0 OR 1" whichs is "0+1"), but the loop in q0 is quite more complex, 1+010*1