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.
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.
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?
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
That Q4 state is useless, it will be considered as dummy state or a dead state since there is no transition to get back from Q4. But, to get a Complete DFA, we need to introduce this dummy state . If we just need a DFA (not complete) we can simply remove Q4 state. Am I right ?
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.
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..
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?
@@MinecraftJesusGaming 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
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?
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!
Thanks ❤.....Comments like this ,plays an important role to clear some confusions
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.
U make the DFA to rexp be simple, Really. The best video for that.
Thank you so much for explaining in such a simple and understandable way. :)
Excellent example. Thanks!
Thanks for this Theory of Computation video! Is there a problem that you want to see done?
Tooo good simply explaination wowwwwww thank uuuu
Very good and funny videos bring a great sense of entertainment!
i cant find the previous lecture that explains the steps, please drop link
What about state q4 equation?? And what if there are multiple accepting states
Wow so easy explanation
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?
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
Big fan Dr Niso Sir
That Q4 state is useless, it will be considered as dummy state or a dead state since there is no transition to get back from Q4. But, to get a Complete DFA, we need to introduce this dummy state . If we just need a DFA (not complete) we can simply remove Q4 state. Am I right ?
clean and wonderful explanation ... Awsome .. : )
watching it before exam thank u
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.
And what if there are more final states than one?
Watch next lecture 😂
Thank you so much sir it helps me a lot🙏🙏🙏🙏🙏
very nice explanation as always !!!
Thank you sir ❣️
if multiple final states are there,what we have to do
check the next videos
thnxxxx sir...........keep UPLOADING
very good videos sir
Nice Sir 😊
Where is part 1 and 2
thank you so much sir
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
If we have several inputs to all situations the Ardem Theory is not helpful. Can you help me?
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*
What does the '+' represent in the final answer?
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.
Thank you 🤧
where is the previous part?
Is this done using Kleene's theorem? please reply
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
Thank you sir
Thank you!
Is this method called Kleens's construction?
It is a DFA. Then why you use epsilon?
As q1 is a final state, epsilon is also accepted
5:19 E+R =< E.R
Where did you get that identity from?
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?
Is the '+' needed in the final answer?
Yes
Thank you sir ji
What if starting state and final states are different both example based on same node with starting and final state.
clean info, thanks
thank you so much
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
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.
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?
Dude I need your help, I'll dm you diagrams
@@MinecraftJesusGaming 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
@@moumitamaity9213 Yeah DFAs/NFAs and automatas are tough, virtually no one has studied it! But I'm taking a class on this topic now.
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
+Neso Academy
plz send me the links of the previous parts(1 and 2) of the "DFA to regular expressions"
Why we take epsilon for eq1 and not for other.....
because it's the initial state
@@GustavoFringe-dv2yg okay
Can anyone find part 1 or part 2? I don't see them in the theory of automata playlist either...
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?
Where is part 2?
Thankyou sir.plx make a video for pda
why has the previous video 51 been deleted
Thankyou sir
can someone confirm whether method used is transitive closure or not?
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
Why u write eqn 4, there is no use of it .
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?
can we write ab=ba ?
sir can you pls tell how to compute when R = RP type of equation is there
@sanskritigupta5795 how we got the final state?
DFA have only one input ina path
But q4 having two I think it's a NFA
A silly doubt! Isn't ab=ba?
Yep ťhey are same.
No ab and ba are not same.
I'm from mathematics and for us it's easy 😂
Ardens theorem
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?
thanku from pakisthan
doesnt work for me
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.
Good
Why you are expand only q1 why not all three
Due to final state
Guys i m not RE for odd no. of 1 by the help of the DFA.........Plz help me out !!!
keep it up
im your bigggest fan!!!
start from NOW!!! shieeeet.... >.< dat was brilliant explanation from A to z!!!
teaching to thk h pr nice example
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.
sir plss i want the previous lec of dfa to regular expressions plss sir update it fast .
Q4 is a not reachable state
no it is a reachable state
q1 = ((ab)*(ba)*)*
(ab+ba)*
(ab+ba)*
52
👍👍👍
Sir vedio put in tamil
Video*
Lewre
Very thanks sir ❤