DFA to Regular Expression Conversion (when the DFA has Multiple Final States)

TOC: DFA to Regular Expression Conversion (when the DFA has Multiple Final States)
This lecture shows how to design the Regular Expression for a given DFA when the DFA has Multiple Final States.
Contribute: www.nesoacademy...
Website ► www.nesoacademy...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...

[@philhearing3659]

You are a great lecturer, thank you for your help!

[@_a_r_un_]

Thanks sir very good explanation 👍

[@pranavnyavanandi9710]

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.

[@jonaskoelker]

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.

[@dhanushsivajaya1356]

Thankyou sir

[@chiluvurideepthi6822]

Crystal clear 😀

[@eku333]

Oh my god this method is the awesome

[@darkblack9958]

Thank you so much!

[@EasyTheory]

Thanks for this Theory of Computation video! Is there a problem that you want to see done?

[@kevinkenny871]

The legend himself! Great work, your channel was very useful!

[@vincenzopalazzo173]

is good to have also the State elimination method :-)

[@manolia4221]

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^+

[@shusenacademy]

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.

[@princevasoya6684]

yes it should be1+

[@harsh_t]

@@princevasoya6684 no

[@harsh_t]

If it was 1^+ , then epsilon wouldn't be accepted. But epsilon should be accepted as q1 is a final state.

[@sumairah9346]

Thanks a lot for this videos........ Very helpful......

[@deependra5233]

Sir, please do some videos on how to find, Regular expression using state elimination method. Please Thank you

[@anshjain257]

yes

[@Nickkxiii]

this method feels a bit easier i will say especially when the dfa is complex or has multiple final states

[@babanparab2370]

thank you naco acadamy ,you are doing really good work

[@akshat680]

yes naco academy is good

[@sierraliao1012]

Thank u very much!

[@Nofaltuguy1]

😮you was has 5 years ago
What are currently pursuing?

[@suvankar54]

Book : Mishra and Chandrasekaran ; Page no 150 (3rd ed).

[@sc5shout]

can q2 = 0*1(1*) be replaced with 0*1+?

[@mobiletechbangla]

Can we use union symbol (U) instead of + symbol?

[@adviceforidevice4536]

no

[@pranavnyavanandi9710]

No, plus is the standard union symbol in regular expressions.

[@divyaanshuagrawal3383]

Thank u sir!

[@ksp2103]

But Q3 is dead state right?
We need to remove that state right?

[@serhatkartopu6239]

yes

[@vikrantbaliyan5075]

very very thank you neso academy

[@harshithshetty8528]

What are u doing now bro😅😅

[@AirTrake1]

Dankeschön

[@abhaynanda1117]

Best video I have ever seen for this topic

[@sarial]

are they same ? (a+b) == (b+a)

[@pranavnyavanandi9710]

Yes they are. But the same does not work for concatenation.
Union is commutative.
Concatenation is not commutative.

[@annawickramasinghe2983]

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.

[@prernasurana8094]

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.

[@mikael673]

life saver!

[@anjalimeena8169]

very helpful sir Thank You

[@mgs_4k198]

Really good, thank you very much

[@varunvarun6022]

Sir..........Its a HUMBLE request, PLZ upload more videos...........

[@shoaibali4309]

Thanks a lot.

[@kriskurti7497]

You sir deserve to get paid as much as football players

[@shoaibali5795]

Hi sir.
We should only find regular expression for the final states or all the states?

[@RohitKumar-po5qt]

Final

[@ziyadelabid679]

Sorry but we have 11*=1+ why we can't use it

[@ahmaddynugroho]

We can
= 0*(e + 11*)
= 0*(e + 1+)
= 0*1*

[@pranavnyavanandi9710]

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.

[@techhelp7657]

@@pranavnyavanandi9710 1+ means all possible string made using 1 except null string (epsilon)

[@User_435gyu6]

What can we write in the lhs of obtained re in the last 5 seconds

[@sreekuttanjs932]

is this state ellimination method

[@rohmanatasi1771]

what if R=QP ??

[@siddiq_sid]

Why didnt we solve q3

[@unstoppable-ayush]

dead state

[@KadelandTheWizard]

When we wrote the last expression h there should be 1 with 0*
0*1+0*11*
because in q2 expression there is q11

[@danishbhatia1734]

Sir, when will you complete the syllabus of TOC

[@Ankit-we8ym]

if you have started, then at least finish it please

[@ShiviNigam-yi4iy]

Bhai mai aapka comment 6 saal baad dekh rha hu......abhi aap kya kr rhe ho

[@_sf_editz1870]

​@@ShiviNigam-yi4iy😂

[@willingdoc]

​@@ShiviNigam-yi4iy lagta hai placement hogya Bhai ka😊😅

[@deadvision22]

you are god

[@neiljohn2637]

53

[@ash57781]

sir can you upload video to convert regular expressions to dfa

[@golfgang7567]

Cool

[@ayeshakhalid4529]

can you plz help me in dfa for the exam pllzzzzzzzzzzzzzzzz?

[@legendneverdiegaminglndg4136]

It's only getting complicated

[@TheKseth]

Sir bacho ko beech me chhodke chale gaye sab rore hain....Aage ki videos to daalo

[@AbhishekSingh-vz7ob]

Sir, when will the new video of this series will be uploaded??

[@Ankit-we8ym]

sir where are you why are you not uploading tutorial??

[@shivanshsoni1776]

SORRY SIR in this viedos have a mistack Q2 state is not asain e empity velue .....

[@swm7f137]

please teach us Context free grimmer

[@Rajesh732-y4l]

hello sir I have a query can u please clarify it???

[@Dexteritye]

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.

[@ChristianBurnsShafer]

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.

[@sonukosuno6803]

But DfA m to 1 hi output hota h na🙄🙄

[@vipulsharma4702]

Nahi ,more than 1 o/p ho Sakta h

[@karthikshinde6739]

i think it is NFA to R.E ...not DFA to R.E..........please cross verif your video

[@aydict]

please cross verify your thinking