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.
![YoungBoy Never Broke Again - Missing Everything [Official Video]](http://i.ytimg.com/vi/dTYeMZGzOzw/mqdefault.jpg)
You are a great lecturer, thank you for your help!
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.
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!
is good to have also the State elimination method :-)
Crystal clear 😀
Thankyou sir
Oh my god this method is the awesome
Book : Mishra and Chandrasekaran ; Page no 150 (3rd ed).
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.
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
Thank you so much!
thank you naco acadamy ,you are doing really good work
yes naco academy is good
Thanks a lot for this videos........ Very helpful......
Best video I have ever seen for this topic
can q2 = 0*1(1*) be replaced with 0*1+?
Thank u sir!
Sir..........Its a HUMBLE request, PLZ upload more videos...........
life saver!
very very thank you neso academy
What are u doing now bro😅😅
But Q3 is dead state right?
We need to remove that state right?
yes
Thank u very much!
😮you was has 5 years ago
What are currently pursuing?
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.
Can we use union symbol (U) instead of + symbol?
no
No, plus is the standard union symbol in regular expressions.
Dankeschön
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.
very helpful sir Thank You
You sir deserve to get paid as much as football players
Hi sir.
We should only find regular expression for the final states or all the states?
Final
Plz someone tell can we follow this method in University exam engineering?
Sir, when will you complete the syllabus of TOC
Really good, thank you very much
is this state ellimination method
Thanks a lot.
what if R=QP ??
Why didnt we solve q3
dead state
When we wrote the last expression h there should be 1 with 0*
0*1+0*11*
because in q2 expression there is q11
53
What can we write in the lhs of obtained re in the last 5 seconds
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
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)
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.
sir can you upload video to convert regular expressions to dfa
Cool
you are god
Sir bacho ko beech me chhodke chale gaye sab rore hain....Aage ki videos to daalo
It's only getting complicated
Sir, when will the new video of this series will be uploaded??
can you plz help me in dfa for the exam pllzzzzzzzzzzzzzzzz?
sir where are you why are you not uploading tutorial??
please teach us Context free grimmer
SORRY SIR in this viedos have a mistack Q2 state is not asain e empity velue .....
hello sir I have a query can u please clarify it???
But DfA m to 1 hi output hota h na🙄🙄
Nahi ,more than 1 o/p ho Sakta h
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.
i think it is NFA to R.E ...not DFA to R.E..........please cross verif your video
please cross verify your thinking