DFA to Regular Expression Conversion
ฝัง
- เผยแพร่เมื่อ 9 ก.พ. 2017
- TOC: DFA to Regular Expression Conversion
This lecture shows how to design the Regular Expression for a given DFA.
Contribute: www.nesoacademy.org/donate
Website ► www.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...
Q4 is left out of the final expression due to the fact that it is a sink state, a state that locks in anything that is not accepted by the machine. The regular expression derived matches the accepting state of the DFA. If you are unsure, go ahead and generate some strings using the regular expression. Then try to see if you can get to an accepting state of the DFA with the generated strings.
Thanks
q4 is the dead state or trap state. I get it 👑
Yeah it's kinda dummy state
good observation
thanks for clearing that!
Book : Mishra and Chandrasekaran ; Page no 149 (3rd ed), example 5.9.
These gonna make no difference in our lives but thanks(!) to our school system, yet we are here... Thank you Neso for helping us fight against this shtty sistem.
So true...
रोते रहो, तुम्हारी जिन्दगी में किसी चीज का वैसे भी कोई काम नहीं होगा ... CS नहीं लेनी चाहिए तुम जैसों को, BCA करते आराम से।
यूट्यूब भी पता नहीं क्यों ऐसी अजीब सी टिपण्णियाँ दिखा रहा है आजकल सबसे ऊपर
@@yash1152 you need to cry sir
@@yash1152lekin BCA ke bad MCA me to ye padhna hi hai at last.
You are the best .... U make everything so simple. I am so thankful to you.
Thank you so much for explaining in such a simple and understandable way. :)
very thankful to you sir,, it is very helpful for, clear explanation. i like the presentation of lectures... hope keep going
U make the DFA to rexp be simple, Really. The best video for that.
Excellent example. Thanks!
clean and wonderful explanation ... Awsome .. : )
Very good and funny videos bring a great sense of entertainment!
Thanks for this Theory of Computation video! Is there a problem that you want to see done?
clean info, thanks
Thank you so much sir it helps me a lot🙏🙏🙏🙏🙏
very nice explanation as always !!!
thnxxxx sir...........keep UPLOADING
Wow so easy explanation
Thank you!
watching it before exam thank u
Thank you sir ❣️
What about state q4 equation?? And what if there are multiple accepting states
Thank you 🤧
thank you so much
Tooo good simply explaination wowwwwww thank uuuu
Thanks sir. How do solve this when there are more accepting states?
Here's what I do!
Make the DFA an NFA (no changes required, but maybe you can eliminate the error state if you know which one it is)
Turn the NFA into a GNFA:
∗ Only one start state, no incoming transitions (make a new start state, and put ε transitions from it to the previous start state)
∗ Only one accept state, no outgoing transitions (make a new accept state, and put ε transitions from it to the accept state)
then the rest is basically the same
sir I have problem to making R.E from a dfa . can you help me. please give me link where I can share you a picture of dfa?so you can easily understand.
how do you write on this board? using mouse or pen? if its stylus you wont be able to move the cursor around like that right? 🤔just curious. can anyone else answer if they know pls?
If we have several inputs to all situations the Ardem Theory is not helpful. Can you help me?
Explain how you determine when to substitute in? In this example you substituted q1 and q2 in the previous exercise there seemed to be selective substitution. Do you automatically substitute equation for the highest state or do you substitute equations for all the states into final state?
Thank you sir
Is this done using Kleene's theorem? please reply
i cant find the previous lecture that explains the steps, please drop link
can someone confirm whether method used is transitive closure or not?
Can anyone find part 1 or part 2? I don't see them in the theory of automata playlist either...
where is the previous part?
very good videos sir
Thankyou sir.plx make a video for pda
Thank you sir ji
What if starting state and final states are different both example based on same node with starting and final state.
why has the previous video 51 been deleted
Thankyou sir
What if q2 q3 isn’t written in terms of q1? What then?
They are bound to be written in terms of q1 cause these states have transitions into q1. Incase q2 q3 weren't the states which would transit to q1 there surely would have been some other state transiting to q1, because q1 is the final state as well, and then they could be written in terms of q1 if not q2q3. Inshort q1 is the initial as well as the final state so there will always be some state which could be written in terms of it.
im your bigggest fan!!!
start from NOW!!! shieeeet.... >.< dat was brilliant explanation from A to z!!!
keep it up
My questions is when you get the q1ab and q1ab from identifiers we know R+ R = R then why did you took ardens theorem there
What if you have something like
q1 = epsilon + q1b + q2a
How do you simplify this?
Depends. What's q2?
q1 = (epsilon + q2a) b* = b* + q2 a b*
q1 = (ab + ba)*
q2 = (ab + ba)* a
q3 = (ab + ba)* b
q4 = (ab + ba)* (aa + bb) (a + b)*
How, in case of q4, (aa +bb) is even happening?
if multiple final states are there,what we have to do
check the next videos
can we write ab=ba ?
+Neso Academy
plz send me the links of the previous parts(1 and 2) of the "DFA to regular expressions"
Where is part 1 and 2
Where is part 2?
can we apply Arden's Theorem if there is an epsilon in P?
No, Arden's Theorem has the assumption that there is no epsilon move.
Good
Is this method called Kleens's construction?
Sir if there would hv been (ab+ab)*
Then could it be written as ab*??
Please any one answer!
S union S is S
so
ab union ab is ab -> ab + ab = ab
Hi All
Could anyone provide a little insight on the DFAs of RE:-a*b(b* +aa* b) and a*b(b* + aa* b)*??
How do I attach the diagrams here?
@Minecraft Jesus Gaming Wow Hi buddy,That's axing and delightful,got to await for a response...after three years...fact is I really forgot what I asked...At that time I was preparing for my country's UGC NET exam for lectureship...and had a look at highly important videos on "Theory of Automata"...,but I have to brush up again from the scratch....to understand the concept....Anyways...thanks a lot for the response...
Om Shanti
Hey tmrw I have my exam and I see you have commented this 4 years ago. What are you currently doing now?
@@10subsonlychallenge66 work from home job..I have completely forgotten automata..so I am sorry I cannot help you.
Regards
@@moumitamaity9213 Its ok I didnt ask for help, I was simply asking you how you're doing.
@@10subsonlychallenge66 lol
And what if there are more final states than one?
Watch next lecture 😂
sir can you pls tell how to compute when R = RP type of equation is there
@sanskritigupta5795 how we got the final state?
5:19 E+R =< E.R
Where did you get that identity from?
Construct a regular expression to denote a language L over ∑= {0,1} accepting all strings of 0’s and 1’s that do not contain substring 011.
Sir this question please..
1*(0+01)*
that was really a good question
I'm from mathematics and for us it's easy 😂
Guys i m not RE for odd no. of 1 by the help of the DFA.........Plz help me out !!!
What if I have many
q1= E
q2=q1 0+q2 1+ q3 0
q3= q1 1+ q2 0 + q3 1
Here it was impossible to solve. But the solution exist when i tested by GNFA
Please can Someone Try solve with Ardens Theorem?
Ardens theorem
thanku from pakisthan
DFA have only one input ina path
But q4 having two I think it's a NFA
Sir, Ur lectures are too gud..but can u plz tell me the name of song at the end of Ur video??
Axol x alex - you ncs
@@vatsalgupta00 thanks bro
It is a DFA. Then why you use epsilon?
As q1 is a final state, epsilon is also accepted
Why we take epsilon for eq1 and not for other.....
because it's the initial state
@@GustavoFringe-dv2yg okay
doesnt work for me
A silly doubt! Isn't ab=ba?
Yep ťhey are same.
No ab and ba are not same.
You only showed a very simple and convenient example. What if there were more accepting states? And what if the accepting states had self loops?
👍👍👍
Why cant we convert it into regular grammer and create regular expression in a easy way?
im sure you can do it like that if you want...
It's the same, you still need to apply Arden's law whenever a recursive production is found.
teaching to thk h pr nice example
52
sir plss i want the previous lec of dfa to regular expressions plss sir update it fast .
q1 = ((ab)*(ba)*)*
(ab+ba)*
(ab+ba)*
Why you are expand only q1 why not all three
Due to final state
then y did we created equation 4 when there wasnt any use of that in the first place
Because that's what the solving algorithm calls for.
Q4 is a not reachable state
no it is a reachable state
Lewre