DFA to Regular Expression State Elimination Method || Lesson 36 | Finite Automata | Learning Monkey

DFA to Regular Expression State Elimination Method
In this class, We discuss DFA to Regular Expression State Elimination Method.
The reader should have prior knowledge of regular expressions. Click Here.
We follow the steps for the state elimination method.
Step 1:
If there exists any incoming edge to the initial state, add a new initial state.
Example:
The below diagram has an incoming edge to the initial state.
Add a new state qi and move to state q0 using epsilon moves. Make qi as the initial state.
The below diagram shows the final diagram after adding a new initial state.
Step 2:
if there exists an outgoing edge to the final state, then create a new final state.
Example:
The below diagram has an outgoing edge to the final state.
We add a new final state qf, and make q2 as the non-final state.
From state q2, we move to qf using epsilon moves.
The below diagram shows the final diagram after adding a new final state.
Step 3:
if there exist multiple non-final states, make them non-final and create a new final state.
The below diagram has two final states q2 and q3.
We change q2 and q3 as non-final states and add a new final state qf.
The states q2 and q3 are joined to qf using epsilon moves.
The below diagram shows the modifications.
We understand a few examples.
Example 1:
The regular expression for the DFA is a*.
Example 2:
The regular expression for the DFA is (a + b)*
We take a or b. We stay on state q0, and we can repeat any number of times.
Example 3:
The regular expression for the DFA is aa.
Example 4:
The regular expression for the DFA is (a + b)
Example 5:
The regular expression for the DFA is (ab)*. We form a cycle with ab.
Now we take an example and find the regular expression using the state elimination method.
The below diagram is our DFA.
For the DFA, we need to add a new initial state and final state because the initial state has an incoming edge. And the final state has an outgoing edge.
The below diagram shows the final automata after adding the initial and final state.
Now we need to eliminate the states between initial and final states.
We can follow any order. We can eliminate q0 first, then q1 or vice versa.
Any order of elimination will give the same output expression.
We eliminate q0 first.
The below diagram shows the Finite automata after eliminating q0.
From state qi to state q1, we move using the expression b*a.
with input b, we move to state q0, and with a, we move to state q1.
Point to understand: we have input edge from state q1 to q0. after eliminating q0, we need to take care of that edge.
So on q1, we write a self-loop with the expression bb*a.
Now we have to eliminate state q1.
State q1 has two self-loops. So we use or condition.
If we eliminate state q1, we get the expression (a + bb*a)*
The final regular expression between state qi and qf is b*a(a + bb*a)*. Because q0 is having self loop.
Link for playlists:
/ @learningmonkey
Link for our website: learningmonkey.in
Follow us on Facebook @ / learningmonkey
Follow us on Instagram @ / learningmonkey1
Follow us on Twitter @ / _learningmonkey
Mail us @ [e-mail]

[@madisenv3989]

Great explanation! Simple and straightforward!

[@dinatjahanmilitasnim4614]

views are less, but he is good

[@g.jayanna4375]

I have watched many videos on this topic but I couldn't understand a single bit... but you saved my day😊 (tom is my exam...)

[@LearningMonkey]

All the best for your exam. Have a great learning in CSE

[@RamashankarSah-o4b]

Sir , this video is very help full for me. thanku so, much for this video sir.

[@LearningMonkey]

Have a great learning in CSE

[@kareemAhmed-nn6ox]

جامد يا واد ي00:03 تحويل DFA إلى تعبير عادي باستخدام طريقة إزالة الحالة 01:17 إنشاء حالة نهائية جديدة في DFA 03:12 تعمل طريقة إزالة الحالة على أتمتة تحويل التعبير العادي. 04:57 طريقة إزالة الحالة لـ DFA للتعبير العادي 06:17 طريقة إزالة الحالة لتحويل DFA إلى تعبير عادي 07:26 طريقة إزالة الحالة في DFA لتحويل التعبير العادي 09:07 طريقة إزالة الحالة في DFA لتحويل التعبير العادي 10:27 طريقة البطل المخترع للبقاء متسقًا

[@Gamer31explore]

Your explanation is ao good sir ,change the thumbnail of this video sir definately you will get views

[@LearningMonkey]

Soon we change. Thank you Have a great learning in CSE

[@sahilbaylr1939]

thanks man.its first time that i understand a lesson from indian guy.respect

[@Elsa_2245]

Tommorow is my exam....I could complete this topic in 15 minutes ...thank you sir

[@LearningMonkey]

All the best

[@SimplyWOW]

Thank you so much for your explanation. Struggled a lot with other channals videos but could easily understand yours, Hatsoff.

[@LearningMonkey]

Thankyou have a great learning in CSE

[@HYDRODROPS]

Boss u r a legend 😎

[@suryodhan3060]

saved my time and exam !

[@ankitt1009]

You saved my day!! Thank you sir!!

[@LearningMonkey]

Have a great learning in CSE

[@sourodipdutta8753]

Your concepts and the way of explanation us very good....❤

[@LearningMonkey]

Tq Have a great learning in CSE

[@udhayakiran1664]

Excellent explanation 🫡

[@LearningMonkey]

Have a great learning in CSE

[@SandipDas-qd1sq]

Superb explanation👍

[@mmllllmm5671]

Best one on KZbin

[@LearningMonkey]

Thank you have a great learning in CSE

[@manum5032]

Nice explanation

[@chandankumarmguthur4356]

Thanks a lot ❤

[@LearningMonkey]

Have a great learning in CSE

[@NadeemAkhtar-h1t]

Too much nice Sir thank You soo much From Pakistan

[@LearningMonkey]

Have a great learning in CSE

[@manupreethgowda476]

Thank you sir Great explanation , but less views improve in thumbnail sir

[@sarthshah5947]

amazing explanation, thanks a lot!!

[@LearningMonkey]

Have a great learning in CSE

[@Ilovepotatofr]

Thanks 👍

[@forthemvps]

🐐

[@WinningEmpire]

bee, bee star, ye 😁

[@rohanwarghade7111]

lol

[@RISHITSTATUS]

Thanks big brother ❤

[@LearningMonkey]

Welcome

[@kareemAhmed-nn6ox]

جامد يا واد يا هندي

[@YasirAli-gw8ry]

Thank u so much brother!

[@motesmarnissi9600]

thanks

[@pannagabm2100]

Thanks a lot sir ❤

[@carloscordero9466]

So great ¡¡¡¡¡

[@anaums413]

thank you sir

[@CodeComet00]

I am kind of confused. Does dfa have the epsilon transition?

[@LearningMonkey]

Dfa do not have epsilon. Taking dfa and converting equal finite automata with epsilon

[@Lilyofc]

🐐🙇

[@TechnomancerBop]

Looked into my soul @ 10:34

[@giwrgoscy294]

THANKS MOM

[@CW-dt2xk]

Nice

[@udaykiranrh]

At second step ,is it outgoinge edge from final state or outgoing edge to final state i am confused,can you please explain this sir

[@LearningMonkey]

Out going edge from final state

[@LearningMonkey]

Have a great learning in CSE

[@LearningMonkey]

Out going edge from final state

[@shahzadawahed2579]

❤️

[@moinundin1221]

yee

[@dibyanshumohanty]

ye

[@KhureshiAbraam9999]

What if same final and start state

[@LearningMonkey]

Move on to next video you will get clarity

[@LearningMonkey]

Move on to the next video you will get clarity

[@xxdanxnad2032]

d

[@sreeharisujith7250]

thanks