In short, when having multiple final states, the final RE for the given DFA is the *union* of the regular expressions found for the individual final states using Arden's theorem. After that, if you wish, you can simplify the RE obtained using suitable rules. That's all.
I like stating exactly the same in multiple steps. Step one: decompose the given automaton (with k accepting states) into k automata each with a single accepting state. Step two: convert the single-accepting-state automata into regular expressions. Step three: take the union of those regular expressions. I find it interesting that step one is a thing one can do. I hadn't thought about it before now. I wonder if it's useful for other purposes. Just like we can do the product construction for arbitrary DFAs, we might define a sum/union construction for isomorphic DFAs (modulo accepting states) such that step 1 is its inverse.
i think the final regular expression should be 0*1+ because if you look at the automata you'll see 0* is leading to a final state but 1* doesn't if you wanna go to q2 then you need at least one 1 so it's 1.1*-> 1^+
Does only DFAs have multiple final states, does NFAs always have only one final state? Iam new to this subject, that's why I am asking this question for my knowledge.
NFAs do have multiple final states, however, given the current state that you are in, there could be multiple next states and could be chosen at random. All the next states can be chosen simultaneously as well. We also do not have to specify as to which state the NFA goes in, provided a certain input.
Can you explain? What is the meaning of 1+. I know 1* means the Kleene Closure of 1, which includes all possible strings that can be made with 1. But what does 1+ mean? I hope you're still in touch with the subject, seeing that this comment is 2 yrs old. If you aren't, somebody else reading may please try and answer.
How would you do DFAs that have 2 incoming arrows for each state. This problem is solvable with this algorithm because q1 has the form of epsilon + q1(0). And we can use Arden's theorem but if there are two arrows pointing towards q1 and q2 also has two arrows, and q3 also has two arrows. This algorithm will fail.
No, the algorithm still works. This is covered in previous videos. Try making an example for yourself where you think it will fail, then test the algorithm.
You are a great lecturer, thank you for your help!
Thanks sir very good explanation 👍
Thanks for this Theory of Computation video! Is there a problem that you want to see done?
The legend himself! Great work, your channel was very useful!
In short, when having multiple final states, the final RE for the given DFA is the *union* of the regular expressions found for the individual final states using Arden's theorem.
After that, if you wish, you can simplify the RE obtained using suitable rules. That's all.
I like stating exactly the same in multiple steps.
Step one: decompose the given automaton (with k accepting states) into k automata each with a single accepting state.
Step two: convert the single-accepting-state automata into regular expressions.
Step three: take the union of those regular expressions.
I find it interesting that step one is a thing one can do. I hadn't thought about it before now. I wonder if it's useful for other purposes.
Just like we can do the product construction for arbitrary DFAs, we might define a sum/union construction for isomorphic DFAs (modulo accepting states) such that step 1 is its inverse.
Crystal clear 😀
Oh my god this method is the awesome
is good to have also the State elimination method :-)
Thankyou sir
Thank you so much!
Thanks a lot for this videos........ Very helpful......
Thank u very much!
😮you was has 5 years ago
What are currently pursuing?
Thank u sir!
Tq sir
i think the final regular expression should be 0*1+ because if you look at the automata you'll see 0* is leading to a final state but 1* doesn't if you wanna go to q2 then you need at least one 1 so it's 1.1*-> 1^+
I think the teacher is right. You see, q1 is also the final state. The string "0" is also accepted and it does not have "1". So, 0*1* is correct.
yes it should be1+
@@princevasoya6684 no
If it was 1^+ , then epsilon wouldn't be accepted. But epsilon should be accepted as q1 is a final state.
thank you naco acadamy ,you are doing really good work
yes naco academy is good
Can we use union symbol (U) instead of + symbol?
no
No, plus is the standard union symbol in regular expressions.
Sir, please do some videos on how to find, Regular expression using state elimination method. Please Thank you
yes
this method feels a bit easier i will say especially when the dfa is complex or has multiple final states
But Q3 is dead state right?
We need to remove that state right?
yes
Book : Mishra and Chandrasekaran ; Page no 150 (3rd ed).
very very thank you neso academy
What are u doing now bro😅😅
Best video I have ever seen for this topic
Dankeschön
can q2 = 0*1(1*) be replaced with 0*1+?
Does only DFAs have multiple final states, does NFAs always have only one final state?
Iam new to this subject, that's why I am asking this question for my knowledge.
NFAs do have multiple final states, however, given the current state that you are in, there could be multiple next states and could be chosen at random. All the next states can be chosen simultaneously as well. We also do not have to specify as to which state the NFA goes in, provided a certain input.
are they same ? (a+b) == (b+a)
Yes they are. But the same does not work for concatenation.
Union is commutative.
Concatenation is not commutative.
Really good, thank you very much
Hi sir.
We should only find regular expression for the final states or all the states?
Final
life saver!
very helpful sir Thank You
Sorry but we have 11*=1+ why we can't use it
We can
= 0*(e + 11*)
= 0*(e + 1+)
= 0*1*
Can you explain? What is the meaning of 1+. I know 1* means the Kleene Closure of 1, which includes all possible strings that can be made with 1.
But what does 1+ mean?
I hope you're still in touch with the subject, seeing that this comment is 2 yrs old. If you aren't, somebody else reading may please try and answer.
@@pranavnyavanandi9710 1+ means all possible string made using 1 except null string (epsilon)
Sir, when will you complete the syllabus of TOC
Thanks a lot.
You sir deserve to get paid as much as football players
Sir..........Its a HUMBLE request, PLZ upload more videos...........
What can we write in the lhs of obtained re in the last 5 seconds
is this state ellimination method
Why didnt we solve q3
dead state
how R is union of both final states? Can anybody explain?
When you have more than one final state, you do a union operation on the regular expressions of those final states.
@@talhamalik3tm 😭did you just explain
what if R=QP ??
Cool
Sir, when will the new video of this series will be uploaded??
sir can you upload video to convert regular expressions to dfa
Plz someone tell can we follow this method in University exam engineering?
what is wrong with this method? its outlined in books as Ardens Theorem...
When we wrote the last expression h there should be 1 with 0*
0*1+0*11*
because in q2 expression there is q11
if you have started, then at least finish it please
Bhai mai aapka comment 6 saal baad dekh rha hu......abhi aap kya kr rhe ho
@@ShiviNigam-yi4iy😂
@@ShiviNigam-yi4iy lagta hai placement hogya Bhai ka😊😅
@@ShiviNigam-yi4iymeh aapka comment 1 saal baad dekh rha aap kya kr rhey ho ab
Sir bacho ko beech me chhodke chale gaye sab rore hain....Aage ki videos to daalo
53
sir where are you why are you not uploading tutorial??
can you plz help me in dfa for the exam pllzzzzzzzzzzzzzzzz?
It's only getting complicated
SORRY SIR in this viedos have a mistack Q2 state is not asain e empity velue .....
you are god
How would you do DFAs that have 2 incoming arrows for each state. This problem is solvable with this algorithm because q1 has the form of epsilon + q1(0). And we can use Arden's theorem but if there are two arrows pointing towards q1 and q2 also has two arrows, and q3 also has two arrows. This algorithm will fail.
No, the algorithm still works. This is covered in previous videos. Try making an example for yourself where you think it will fail, then test the algorithm.
hello sir I have a query can u please clarify it???
please teach us Context free grimmer
But DfA m to 1 hi output hota h na🙄🙄
Nahi ,more than 1 o/p ho Sakta h
i think it is NFA to R.E ...not DFA to R.E..........please cross verif your video
please cross verify your thinking