Conversion of NFA to DFA (Example 2)

TOC: Problem Number 2 on Conversion of Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).
Topics discussed:
This lecture shows how to convert a given NFA to its equivalent DFA using the Subset Construction method.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy...
Website ► www.nesoacademy...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #NFAtoDFA #NFA #DFA #AutomataTheory

[@prasathmsd0760]

All the best for tomorrow's exam mate😂

[@GauravRao09]

Thanks bro my exam is tommorow

[@futurehofer1564]

thanks lol

[@4bdisa]

🤣👍

[@mhmd1759]

lol my exam after 10 hours

[@blacklion9901]

I'm going to exam hall while watching 😂

[@mohdamaan5551]

after 6 years ,still helping passing semester exams.

[@ompadhi1476]

fr brother

[@soumyaranjansamalkiit]

yeh!

[@zarefgamz2515]

very true

[@Ogg_skimmer]

True bro

[@deveshchahar4303]

Passing!! bhai isse padke to top hai

[@tanvirhasanmonir1627]

Millions of thanks to you dear sir. Your tutorial is the best material to learn "Theory of Computation"

[@assaqwwq]

i love it when he asks "what is the meaning of this?". my gut reaction is of "i dont know, its not my fault"

[@bestof1506]

Is this a reference to something?

[@phoenixultimate8253]

no its just a funny reaction

[@aadisupersonic]

lol.. relatable enough..

[@HARIHaran-ks7wp]

lmao so true

[@AkbarAli-wx5ld]

😂😂😂

[@RahilKhan-jt9ut]

ans : should not start with 'ba' and must have odd no of b(s) at the end

[@sgr2683]

correct!! Thanks

[@dheepakraaj8352]

But abab is accepted ?

[@Nishaang]

@@dheepakraaj8352 strings with not starting with ba and having odd no of b's and ending with odd no. of b's

[@paramsavalia7900]

for ababab, it is wrong according to your condition

[@RahilKhan-jt9ut]

@@paramsavalia7900 yeah you're right

[@capitalofcambrom]

These examples are fantastic. Thanks for explaining it step-by-step!

[@Netugi]

Right? It really helps having every detail explained clearly, so I can see what the process actually is. Was about pulling my hair out doing my class assignment because my notes weren't the best.

[@justinphilip3502]

2 years back this day,best tutorial ever

[@siddhantgarodia3381]

still the best lol

[@supersakib62]

Assignment Answer could be:
L = {Set of all strings over (a,b) that ends with 'b' but does not start with 'ba' and has odd number of 'b' incase of no 'a' and does not contain 'ababa'}
For both DFA abd NFA : {set of all strings over (0, 1) that does not start with 'ba' and ends with 'b' and has odd number of 'b'}
1) ends with an odd number of b’s
2) cannot start with “ba”
3) cannot contain “baba” after an even number of b’s or any number of a’s

[@dakshdixit7286]

bbb is answer according to your logic but it will fail
So it think answer should be {b, does not start with 'ba' and ends with 'ab' and has odd number of 'b'}

[@avinashmishra9163]

@@dakshdixit7286 So, what is right task done in this question?

[@dakshdixit7286]

@@avinashmishra9163 i wrote in my comment

[@egetahayamaner7094]

@@dakshdixit7286 How does bbb fail it is in the accepting state.

[@msbrdmr]

I think its {dont start with ba, end with b or ab}

[@himanshugupta3028]

It accepts the string which satisfies following conditions: -
1. It should not start with 'ba'.
2. Total Number of b's in the string should be odd.
3. The string should end with odd number of b's.

[@korhandenizakn6107]

Are you sure with your 2. sentence. Try "abaab".

[@niteshmodi5468]

abab is accepted

[@sahil.sjiwane]

This question came to my university paper. Thanks for the help 🌟

[@siyasahoo4965]

The Q are really helping clearing the concept. Even after 7 years it's still helpful ❤

[@chocolateboyanubhab7340]

i am really a fan of your teaching...such complicated topics are being taught in an easy and simply wap...HATS OFF to you sir...Lots of love from the bottom of my heart.....

[@lone_wolf2020]

The given NFA and it's equivalent DFA accepts any strings made with {a, b} and that must have a single 'b' at the end.
Thanks for the lecture sir.
---------

[@user-uz3rw9hh3k]

incorrect try baab

[@tomzhang3597]

1) ends with an odd number of b’s
2) cannot start with “ba”
3) cannot contain “baba” after an even number of b’s or any number of a’s

[@mohak23898]

Correct

[@syedqamberalikazmi1001]

You're so genious

[@OllieGee333]

#3 is not correct, "bbabab" is accepted.

[@poonamshekhawat1576]

i.e strings ends with 'a((b)^n+1) ; n={0,1,....}

[@OllieGee333]

Mayurdeep Pathak thats 1 b... thats an odd number of b's

[@stefangjorgjevski1990]

answer: case1 : strings can contain only one character 'b' ,
case 2: start with 'a' followed by as much 'a' as you want and end with an odd number of 'b's

[@smortlogician9258]

it can also accept strings with no 'a's and only odd no. of 'b'.
like if you see, it can accept 'b' or 'bbb' or 'bbbbb' and so on..

[@rbek]

@@smortlogician9258 yes That is exactly what i was about to say

[@stefangjorgjevski1990]

@@smortlogician9258 so it would be 3 cases?

[@smortlogician9258]

@@stefangjorgjevski1990 no still 2 cases. As a single b is included in the case of odd no
Of bs

[@smortlogician9258]

@@stefangjorgjevski1990 I think the best answer would be that this FSM accepts string of the form (a^n)(b^m) where n is a whole no. and m is a natural number

[@yuvethiekasri606]

Assignment Answer could be:
L = {Set of all strings over (a,b) that ends with 'b' but does not start with 'ba' and has odd number of 'b' incase of no 'a' and does not contain 'ababa'}

[@youucanexamprep]

Strings which are accepted in NFA and DFA both are -
1. Only b.
2. End with b.
3. End with ab.

[@anubhavsingh9852]

wrong,, fails for ababab ,bb,baab etc etc

[@akshatgoyal4035]

Great video! Assignment question answer: It takes a string ending with odd number of b to reach it's final state.

[@lokeshyanamandra7775]

But in some cases b Is even bro,so I think so the result will end with b.

[@younisthetrainer8461]

@@lokeshyanamandra7775 no it takes only odd number of b's

[@rohanghauri1935]

try "abbabab"

[@AcezeroGame]

I think it accept every string ending with b

[@robintheunleashed2025]

@@AcezeroGame yeah its string ending with b

[@SumitKumar-ne9kc]

So answer of the last question is :
string must contain odd number of b's after the first 'a' from the right side and also it must not contain odd number of b's before first 'a' from the left side.
all string which follow the above constraint will accept by the given NFA
please correct me, if I'm wrong.

[@lone_wolf2020]

i think -> The given NFA and it's equivalent DFA accepts any strings made with {a, b} and that must have a single 'b' at the end.
try input abab --where no odd numbers of b is present.
Feel free to correct me if you think i'm making any mistake.

[@viveksharma5672]

Thanks Neso Academy you are doing a great job for students like us. 👍

[@mirzakariaislam610]

Thanks a lot. Today is my exam. I took my preparation through your lecture.

[@RohitRaj-sf6th]

For both DFA abd NFA, {set of all strings over (a, b) that ends with odd number of 'b'.}

[@karanvenkateshupamanyuise-9407]

it accepts "abab" though. (you've probably already passed atc lol but just saying)

[@stefanif2002]

doesn't accept babb

[@thyagarajarathnampillai5391]

Assignment answer. String cannot start with 'ba', ends with odd number of b's or at most 2 consecutive 'ab's

[@ruili7941]

{a*b, any number of 'a' end with odd number of 'b'}

[@anetaivanicova1709]

it accepts strings that start with a*n, n=0,1,2.. and followed by b*n/2 != 0

[@ProfessionalAmateurQ]

but it can also accept strings that start with 'b', no?

[@dereck2199]

Ans :-
1. it will take odd numbers of 'b'
2. it will take odd number of 'b' end will be followed by 'ab'
example :- ''bbb', 'bbbab' this will be accpected by the DFA

[@arsh5587]

Nah bro, abab is also accepted in that dfa , according to me it's the collection of string ends with b

[@dereck2199]

@@arsh5587 i mentioned end with ab.... That abab ends with ab..... So it is accepted

[@arsh5587]

@@dereck2199 yeH u r right but b can be even also

[@mozammalhossain968]

The language accepts strings
1. Doesn't start with 'ba' AND
2. Odds number of 'b' in sequence from the ends

[@sahilnaik3079]

That is not correct according to your explanation ababab should be accepted.
But your answer is close. Some modification is required

[@sstxixo3975]

My answer: All words ending in "b", can't start with "ba", can't contain "baba" (all applied at the same time)
Example words that work: b, a(a)b, bb(a)b, bbbbb(bb), a(a)baa(a)b, bb(a)baab;
Example words that break the automat: ababa, ba, a(a)baba;
Note: Brackets symbolize periods such as in some representations of rational numbers.

[@nas.a3512]

"bb" is also excluded. Both the DFA and NFA representation do not accept any example words that end with the input "abb"

[@guoweih7339]

The answer should be: (a +(a+bb)b*a + bb)*b
In order to do this, you need to first watch lecture 51.

[@itachi-senpaii]

thanks

[@MischievousSoul]

It's ans is the strings that ends with odd no of B
Because it accepts every string that has odd no of B and doesnt focus on the no of a and b it had in between

[@anubhavsingh9852]

string abab is accepted.what now ;-

[@rajasarodar3628]

NFA : set of all strings over {a,b} that ending with b
DFA:set of string b or atleast one 'a' followed by a 'b'

[@maxba2543]

aabb?

[@IbrahimAli-mj8ye]

The machine accepts the string 'b' or a string of at least one 'a' followed by a 'b'.

[@MrLarryLicious]

THANK YOU FOR YOUR EXISTENCE

[@rajashekar4171]

Hi

[@pulkitdhirana215]

Best tutor ever on YT

[@user-rx7dz5wn5g]

L = { set of all strings over (a,b) that contain just 'b' or that starts with 'a' and ends with 'a*b' or that starts with 'bb' and ends with 'a*b'}

[@rhaypapenfuss]

Neso academy is such a life saver

[@gautamkatyal9966]

It accepts the String start from a and nth number of a's and ends with b or String starts with b followed by b and nth number of a's and end with b.

[@rohitnair9022]

Why b and not nth number of b's?

[@amalalzaben3709]

thank you so much you really saved me ,i have an exam next week and i'm ready because of you

[@jenilpatel5610]

Using Arden's Theorem on Above DFA, I get my regular expression solution as:
L = ( (b) + ( a + bb )(a + bb + baa + babb)*(bab) )
Which is 100% correct but help me out with reducing it...
To claritfy my answer in first bracket there option between either 'b' or whole right side term.
in that term, there's three concatinated strings.
1st string has two options 'a' or 'bb'
2nd string has 4 options which is starred (*) which means it can be used 0 or more times.
3rd string is fixed with 'bab'

[@navabshaik7280]

It's a dad of all channels to understand kinly the Automata &TOC

[@vrushaligholap6647]

GREAT EXPLANATION SIR! YOU MADE IT VERY SIMPLE AND EASY.

[@BillPark-ey6ih]

This guy saved my life.

[@buzzfeedRED]

YOU MUST TELL THE ANSWERS OF THE ASSIGNMENT YOU HAVE GIVEN IN YOUR VIDEOS ,

[@sundarraj6509]

I think it’s answer is that “the string that either end with ‘b’ or ‘ab’”.

[@Adithyan7274]

@@sundarraj6509 ​you are correct but there's one more.. the number of ' b ' should be odd, because even number of ' b ' ends in the state AB which is not the final state.

[@ganeshpandeyKing_Brian]

@@Adithyan7274 The machine accepts string "abab" so i guess there's more to it than just odd numbers of "b".

[@abelii8726]

i think if the number of 'b' is either prime or odd then it's accepted by the machine.

[@yokeshnsr1976]

@@abelii8726 but 'abbbab' is also accepted

[@danteeep]

far the best video explanation with an example for the conversion of NFA to DFA. thank you so much for this !!!!!!

[@user-iu9xo2xm2z]

Bhai aap kon se college se the? Or aapka college me placements ka kya scene tha/hai, Or aapka placement hua?

[@saurabhmourya7271]

L: {accepts the strings which neither start or end with 'ba'}

[@elisamutiofficial2245]

Thank you Sir. When I learn with your videos , I understand everything thing.

[@raviranjan1810]

your videos I just awesome, no words god-level explanation with full concept

[@pranayaghimire1122]

Neso academy is heart of csit students.

[@user-iu9xo2xm2z]

Bhai aap kon se college se the? Or aapka college me placements ka kya scene tha/hai, Or aapka placement hua?

[@shumailasaifi]

i first time create diagram by myself feeling good. Thank you sir. Allah-humma-Barik to you are your family.

[@it-a-024-ibrahimfarwahaffa2]

I think he is not a Muslim ....

[@pranavagarwal4827]

the string that only ends with odd number of b is allowed
and if the string starts with b and has to contain a , then their must be at least 2 b in the start

[@kingbond470]

On condition and---- ab🤔?? And for odd number abbbab??

[@shivamjaiswal7950]

@@kingbond470 the string that contain odd no. of b at end

[@kingbond470]

@@shivamjaiswal7950 abbbab??

[@RittickJana]

Thank you so much.... I express my sincere gratitude to you.

[@asefahmed11]

After 6 years, still helping me

[@adityakukade3691]

all strings ending with b or odd no of b's or a followed by odd no of b's

[@yahyairfan1159]

Starting with a and ending with odd b,s OR starting and ending with a 'b' only

[@MyAsdfqwe]

this and union, starts with even b's followed by infinite a's with even b's and ends with b.

[@yuyao4008]

way much better than my lecturer thanks a lot.

[@aniketkumar9621]

string that accepts all the string over {a,b} that starts from a & must end with ab

[@sagarr3964]

It's 2021 , and tomorrow is my exam I have no worries after watching these videos

[@umeshvyas86]

I think that this DFA/NFA accepts all strings which end with b^k sub string where k is an odd number.

[@phantomv1951]

L={set of all string over 'a' and 'b' that ends with 'ab'}

[@TEMSGENGETIE]

it is very very very good tutorial live in ethiopia

[@yasina63]

I found out NFA is stated based on the current input. The DFA has a unique transition from each state to every input. Thanks a million. ❤️🙏
Today I have a final exam. I hope I will get an A+

[@shanmugapriya7554]

L={set of all strings with 0 or a's and end with odd number of b's}

[@aayushve426]

Answer to the assignment: set of strings on (a,b) such that no 'ba' string is present and odd no. of b's at end of string.

[@randomstuff5714]

ASSIGNMENT :- a string which starts with even number of 'b' and ends with odd number of 'b'

[@rajearyan]

i dont think it is even number of b's. It is odd only.

[@okko7788]

But abab works but shouldn't be accepted according to your definition

[@randomstuff5714]

@@rajearyan No, It must be even also. Example- "ba" won't be accepted but it still contains odd number of b's.

[@randomstuff5714]

@@okko7788 No, it will be accepted according to my definition. "abab" is starting with 0- 'b' and zero is an even number and it is ending with 1- 'b' and one is an odd number.

[@randomstuff5714]

I can see that my definition is wrong. one condition is also there, that after odd number of 'b' there should not be 'aba'.

[@longlivefreedom]

Sometimes I found your videos more useful than university lectures.

[@AnukiranGhosh]

all the time

[@Nomnomnom165]

all the time 😂

[@AnimeManiaa]

String that contains any no of a's followed by 0 or even no of b's and end with odd no of b's

[@tolulopemalomo8922]

I think the DFA/NFA accepts all strings over { a , b } that end with an odd number of b-s. Please let me know if I'm right.

[@SahibpreetKaur]

I think it's not odd number of b-s but rather all strings ending with a single "b". For example: b, ab, aab, abab. But NOT abb or aabb or aabbb.

[@Viggen66]

Thanks for this teaching, awesome lecture

[@gameskiduniya]

you deserve my math teacher's salary

[@arunkumarsundaram9941]

Accepts a string ending with odd number of b's unless one of the following is true:
1. String starts with 'ba'
2. There is an occurrence of 'aba' after an odd number of b's

[@alan2211]

No, strings starting with 'ba' will end up in the dead state.

[@TariqueGauri]

This condition is not true for aabbb

[@shubhrajyotipoddar1684]

set of all strings starts with {a, b} that ends with odd no of b

[@prashanthi8492]

the answer to the last question is
the string that contains only odd no.of b's, strings that ends with oddno.of b's.

[@markxavior]

Excellent tutorial professor.

[@shrunkhalawankhede2611]

VERY NICE EXPLANATION. NICE ACADEMY ROCK IS ALL SUBJECTS

[@frankhilgenberg7310]

ASSIGNMENT: L = {Set of all strings over (a, b) that ends with a odd number of 'b's}

[@anubhavsingh9852]

check it for ababab

[@frankhilgenberg7310]

ups! With ababab I will end in state D and this is not a final state. So - let me think about it again ;-)

[@SaurabhGupta-sx4jy]

L={Set of all strings over (a,b) that ends with 'b' , 'bbb' or 'ab'}

[@seifhossam559]

Thanks for your help

[@jay3101]

for NFA sol :accepted string ending with. (b) followed by even no of (a).

[@VishalSharma-ks6ip]

ab is also a string which is accepted.... Here a is not even

[@poojithatummala1752]

It accepts the string that starts with 'a and ends with b' & string 'b'.

[@deepakvaishnav9780]

It is accepting the strings that end with sequence of 'b' having odd numbers of b consecutively

[@healthandenvironment2998]

Amazing Sir!! You deserve a subscriber. I HAVE SUBSCRIBED

[@utshodas001]

great video. is the answer " a^n b^2n+1 n>=0 "?

[@ajaykarthik01]

thankyou please complete the compiler design tutorial as soon as possible

[@navaneeth2000-qc]

Thankyou very much for this valuable class

[@AviralBangar777]

very good video easy explanation thank you

[@djmaster1110]

Very well explained

[@azuboof]

I'm supposing the design style doesnt matter, meaning where i put C or D like in up or down direction as long as all the arrows are correct

[@java_with_yash]

This DFA accepts a string which is ending with 'ab' or has odd number of b's in it.

[@manishshee6990]

Not end with 'ab', it ends with odd no of 'b'

[@java_with_yash]

@@manishshee6990 bro check for 'aab' ?

[@manishshee6990]

@@java_with_yash yes in NFA it goes to 'C' state & in DFA it goes to 'BC' state

[@java_with_yash]

@@manishshee6990 bro string is acceptable or not ? 'aab'...

[@java_with_yash]

@@manishshee6990 yes so ..c and bc both are final states..so the string is accepted.

[@navabshaik7280]

It accepting strings of a&b's which having atleast one b and should ends with b only

[@rohanwarghade7111]

thanks sir

[@arkadiptadas4148]

Set of all strings over (a, b) that ends with 'b'

[@akshitmaheshwari5430]

abb is not accepted

[@shivamjaiswal7950]

set of all string that ends with b and contain odd no. of b.

[@deepanshukasaudhan6723]

any sting which ends with odd no's of b and do not start with ba will be a accepting string

[@soumikmandal2085]

L={don't start with ba and ends with an odd number of b's for set of all strings over {a,b}}

[@smortlogician9258]

I think the best answer would be that this FSM accepts string of the form (a^n)(b^m) where n is a whole no. and m is an odd natural number

[@mukulbikaspahari6583]

I think it will accept strings if it ends with odd number of b

[@mdsalehan5683]

Any strings end with odd no. Of 'b' which does not starts with 'ab' will accept by this DFA .... am I ri8 sir?

[@thyagarajarathnampillai5391]

Assignment answer. String cannot start with 'ba', ends with odd number of b's or at most 2 consecutive 'ab's

[@snehalmali9630]

Strings will be accepted which doesn't start with 'ba' and containing odd no of 'b's and end with either single 'b' or 'a' followed by 'b'.
Is it the right answer, Sir?

[@ArunKumar-mv3qj]

I think answer will be, accept any string over {a, b}, that ends with 'ab', except starting string 'ba'.
Is it right??

[@radhaharini5758]

Really thank you so much sir best tutorial 👌

[@rajashekar4171]

Please you have any notes

[@sandipdas5684]

Your tutorial on this subject is best sir... Respectfully thank you so much sir...

[@dharmarajbista3919]

Thankyou so much sir
It help me a lot

[@deniztopay306]

I guess what is this for is strings with starts with an 'a' and has an odd number of 'b'.

[@shironas6109]

You have been a great help 🙏