Conversion of Regular Expression to Finite Automata - Examples (Part 2)

แชร์
ฝัง
  • เผยแพร่เมื่อ 23 ธ.ค. 2024

ความคิดเห็น • 195

  • @cyber_dbs
    @cyber_dbs 2 ปีที่แล้ว +4

    Thanks!

  • @mayursandbhor8824
    @mayursandbhor8824 7 ปีที่แล้ว +58

    can we have single final state instead of creating new final state 6?.. we can directly move from state 5 to state 4 on getting the symbol b

    • @Aditop979
      @Aditop979 ปีที่แล้ว +5

      we can also remove the state 5 and connect state 2 to state 4 by accepting b

    • @garv1202
      @garv1202 10 หลายเดือนก่อน +1

      @@Aditop979but we can't have the self loop on 2

    • @AdityaPalande-y6l
      @AdityaPalande-y6l 9 หลายเดือนก่อน

      @@garv1202 why???

    • @hrishiv
      @hrishiv 9 หลายเดือนก่อน +6

      @@AdityaPalande-y6l because that would allow 'aaabb' because you could take the loop any number of times for a then have two bs, which isn't in the regex.

  • @uguryucestudent281
    @uguryucestudent281 9 หลายเดือนก่อน +5

    do we really need new final state or can we move from 5 to 4 with b? (05:00)

  • @mistusural
    @mistusural 7 ปีที่แล้ว +99

    sir pleace kindly explain why their are 2 final state , we can easily connect it from 5 to 4 by input b... then why should you take another state????????????

    • @rhlmshr8
      @rhlmshr8 6 ปีที่แล้ว +16

      It was not needed. Just a way to do that. I agree with your way too

    • @IonutE
      @IonutE 6 ปีที่แล้ว +28

      I belive the point is not creating minimal nfa , but simply a working nfa

    • @chouaibbenali5201
      @chouaibbenali5201 6 ปีที่แล้ว +10

      You can even use the 2nd state to link the state 5 using the symbol a

    • @elyasaf755
      @elyasaf755 5 ปีที่แล้ว +8

      You are correct. If you use identities, then you can get to this equivalent regex: (a+b)*a(b+a*)b
      And you can clearly see that it always ends with b, which means only 1 final state.
      The way he did is just "Straight forward". after using that method, you can use minimization methods to minimize the automata.

    • @BlizZarDaSh
      @BlizZarDaSh 5 ปีที่แล้ว +1

      @Tswaitswai Mochaki No, He's actually correct, it makes sense. Since nothing is specified it is possible.

  • @piyushjain7223
    @piyushjain7223 ปีที่แล้ว +3

    00:01 Conversion of regular expression to finite automata example
    00:47 Constructing a finite automaton for a given regular expression.
    01:42 Creation of states for a given sequence of symbols
    02:28 Transition between states based on input symbols
    03:17 Understanding the difference between a plus and closure in regular expressions
    04:07 Demonstrating the conversion of a regular expression to a finite automaton.
    04:49 The final automata is an NFA
    05:36 Conversion of NFA to DFA is possible
    Crafted by Merlin AI.

  • @SuperDigitallady0513
    @SuperDigitallady0513 5 ปีที่แล้ว +12

    Hello sir it is very uses full video, I have question here can we follow state 5 directly to state 4. Is it must adding state 6 here.

  • @sharangdharshree
    @sharangdharshree ปีที่แล้ว +11

    can we go from state 5 to 4 instead of 6 on input b ? so that we have only one final state

    • @mistersir3185
      @mistersir3185 ปีที่แล้ว +1

      nope, only if it was (a^+ . b)^*

    • @lalitsingh1266
      @lalitsingh1266 10 หลายเดือนก่อน +1

      @@mistersir3185 how bro can u explain

  • @abhishekjaiswal4168
    @abhishekjaiswal4168 7 ปีที่แล้ว +10

    plz sir complete this series
    actually this series is very helpful to study
    I have toc in my current sem

    • @debmalooo2286
      @debmalooo2286 6 หลายเดือนก่อน +1

      hello just curious to know what r u doing now??plzz

  • @abdulahad9577
    @abdulahad9577 6 ปีที่แล้ว +43

    hey neso academy, can we join state 5 to state 4 with transition 'b'??

    • @ankitacharjee1504
      @ankitacharjee1504 3 ปีที่แล้ว +7

      I also have the same question.

    • @minamehak7270
      @minamehak7270 3 ปีที่แล้ว +4

      I was also thinking about that

    • @sameeranerella1120
      @sameeranerella1120 3 ปีที่แล้ว +1

      We can join

    • @HarshYadav-qz2bm
      @HarshYadav-qz2bm 3 ปีที่แล้ว +2

      yes we can join because we have to reach the final state only

    • @riyagupta8827
      @riyagupta8827 3 ปีที่แล้ว +8

      @@ankitacharjee1504
      No, we can't join with state 4 as in the expression given that either we get abb or a+b in the end
      That's why we will start from state 1 again
      Here will be the choice in between path either 1 to 4
      Or. 1 to 6. depending on the output

  • @kevinstratford2727
    @kevinstratford2727 ปีที่แล้ว +3

    sir can't we combine both the final states G and 4 together; i.e state 5 on i/p b goest to 4??

  • @pavanteja1738
    @pavanteja1738 7 ปีที่แล้ว +24

    plz complete the playlist..we have a subject called flat(finite language and autometa theory). ....we need videos on -grammer formalism,control free grammer,push down autometa,turning machine, comparability theory

  • @raghavsidana3812
    @raghavsidana3812 7 ปีที่แล้ว +3

    What is thompson construction method??
    Is it a way to convert RE to NFA??

  • @ΔημοσθένηςΑνδρικόπουλος
    @ΔημοσθένηςΑνδρικόπουλος ปีที่แล้ว +1

    If the regex was (a+b)*(abb+a*b) how would the FA be ? Because a* means also ε, so we can reach the final state only with b . Would be the same adding only a b-> from state 1 to state 4? Because the loop from (a+b)* covers the possibility of a* ≠ε

  • @KENNETHANTONYJOHNBCE
    @KENNETHANTONYJOHNBCE 7 ปีที่แล้ว +23

    Sir, instead of creating a new state '6' for the final state is it correct if state '5' goes to state '4' on getting input b?

    • @parikshit3022
      @parikshit3022 2 ปีที่แล้ว +1

      sahi kehra h bhai

    • @anupamashok7135
      @anupamashok7135 2 ปีที่แล้ว

      Could go tostate 3 only

    • @akashchoudhary8162
      @akashchoudhary8162 2 ปีที่แล้ว

      @@anupamashok7135 No you can't go to state 3. State 3 is not final state due to which the string would become (a^+)bb

  • @lovestehloz
    @lovestehloz 3 ปีที่แล้ว +3

    Isn’t the state ambiguous coming from state 1? If input ‘a’ is received after state 1, how does it know which state to go to 2 or 5?

  • @hmzzz4621
    @hmzzz4621 7 หลายเดือนก่อน +1

    Is it possible to connect state 5 to state 4, instead of connecting it to state 6

  • @abdulislam4786
    @abdulislam4786 2 ปีที่แล้ว +1

    Sir FA mn 2 'final states' nhi ati yh toh TG mn ati hn?

  • @pankajkumarray6716
    @pankajkumarray6716 7 ปีที่แล้ว +1

    All videos are awesome.Please unload further videos.

  • @cassiakahwage4130
    @cassiakahwage4130 6 หลายเดือนก่อน

    Dear professor, could this expression be represented by a deterministic finite automaton? Why are there 3 possible transitions for "a"?

  • @sudhanshubhardwaj202
    @sudhanshubhardwaj202 5 ปีที่แล้ว +2

    Can we ignore 5 and 6, instead we can make a self transition on state 2 for input 'a', and make both state 3 and 4 as final states??????????

  • @Comebacktoalmighty
    @Comebacktoalmighty 6 ปีที่แล้ว +1

    There is possible to make two final states??

  • @kadheermax1617
    @kadheermax1617 2 ปีที่แล้ว

    How can we have two 'a' for state 1?,Rule is that one state should have an input only one time right?

  • @ramapriya6702
    @ramapriya6702 3 ปีที่แล้ว +1

    in the before lecture a(bc)* has this but u didnt take a self loop but now in here taking self loop, whts the diff in before one

  • @omar-senpaiii
    @omar-senpaiii 4 ปีที่แล้ว +6

    Thank you Sir for your great explanation!
    I have converted it to a DFA form, and I just want to know if my final DFA graph is correct, the DFA consists of (1) as an initial state and (125),(136),(14) all as final states and I have tested a lot of strings ,which follow that regular expression, and all of them were correct!

    • @aashritamutkiri5071
      @aashritamutkiri5071 3 ปีที่แล้ว +5

      You did right. But, final states are (136) and (14) not (125).

  • @andyoviedo3460
    @andyoviedo3460 8 หลายเดือนก่อน

    Cant I choose to go from 5 directly to 4 using b?? Or why is it necessary to create a state 6.

  • @bernz1973
    @bernz1973 2 ปีที่แล้ว +1

    so state 1 is not an accept state? if so, why?

  • @lamaspacos
    @lamaspacos 7 หลายเดือนก่อน +1

    (abb+a†b)=a(bb+a*), where † stands por “+”.

  • @nandinisingh5250
    @nandinisingh5250 10 หลายเดือนก่อน

    5:44 There can be two final states

  • @_singh_piyush_
    @_singh_piyush_ 4 ปีที่แล้ว +1

    Thank you so much for the help ❤️

  • @042_dikshasakhare6
    @042_dikshasakhare6 2 ปีที่แล้ว +1

    life saver.

  • @umeshpatidar5746
    @umeshpatidar5746 7 ปีที่แล้ว +1

    pls complete this series

  • @Apoorvpandey
    @Apoorvpandey 3 ปีที่แล้ว

    In first part (a+b)* why didn't we made state S1 to S2 on input a,b?
    I'm confused with these examples

  • @naziyabano5801
    @naziyabano5801 หลายเดือนก่อน

    I think there's no need of 5th state also we can just directly connect 1 to 4 with a transition of b .Can anyone suggest me string which will not accept by my finite automata as discussed earlier

  • @MalakHassun-yt8lk
    @MalakHassun-yt8lk 6 หลายเดือนก่อน

    Please, I have an exam tomorrow and I have a question for the sake of theorem ardens. I just ignore every equation for q1 and don't do it on the basis of what I missed??

  • @shridhardeshpande1383
    @shridhardeshpande1383 7 ปีที่แล้ว +4

    can you plz upload the videos of pumping lemma , pushdown automata , context free grammars as soon as possible we having exams in next few days .......

  • @joelvzach
    @joelvzach 6 ปีที่แล้ว +5

    How would we have solved this question if, in the end, it was a* instead of a+ ?

    • @ShayantanSantra
      @ShayantanSantra 5 ปีที่แล้ว

      I guess we would have taken b first then self looping a

    • @atifayaz3495
      @atifayaz3495 5 ปีที่แล้ว +7

      Since we have to make automata, so we can also make NFA. We can transit state 1 to 5 over epsilon.

  • @Mihir_Jain
    @Mihir_Jain 9 หลายเดือนก่อน

    can we take b output from 5 to directly on 4. is it possible if we remove the 6 node and directly connect the output of 5 to input of 4

  • @rishiroshansingh8865
    @rishiroshansingh8865 4 ปีที่แล้ว +3

    since a single b can also be represented by this Regular expression,
    1->5 should be through epsilon, not 'a'.
    5--->4 through 'b' is definitely possible making 6 is useless,
    but since its NFA. 5-->4 isn't necessary

    • @volkanulker6432
      @volkanulker6432 3 ปีที่แล้ว

      I agree with you about 1 -> 5 should be epsilon because when we use 'a' there is no chance to get 'epsilon+b' or just 'b' in that branch.

  • @tharindumarapana6670
    @tharindumarapana6670 2 ปีที่แล้ว

    Very clear explanations both parts. Thanks much

  • @abhivk5176
    @abhivk5176 ปีที่แล้ว

    can we put a loop of 'a' on state 2. and make state 3 also as final. that too will statisfy the case instead of drawing more states like 5th and 6th!

  • @rimakar9955
    @rimakar9955 5 ปีที่แล้ว

    sir you have told that or operations has only one destination states then why you have done two final states for the or operation abb|a*b

  • @buzzfeedRED
    @buzzfeedRED 6 ปีที่แล้ว

    +Neso Academy In the previous video why we not make a self loop of (bc) in ques 3
    Please explain ????/??

  • @chandanbhadrala5749
    @chandanbhadrala5749 7 ปีที่แล้ว

    which wacom product you are using? if you can tell that would be quite help

  • @aniketmalhotra989
    @aniketmalhotra989 2 ปีที่แล้ว +1

    Sir can we join our 5 state to the 4th state. So that we have only 1 end state.

  • @ishanmishra5416
    @ishanmishra5416 ปีที่แล้ว

    Can we go from 1 to 3 with input a and then its complete?

  • @ozba
    @ozba 9 หลายเดือนก่อน

    we can turn a to state 2. and state 3 can be our second final state. instead of using state 5 and 6

  • @snehalnandekar4485
    @snehalnandekar4485 ปีที่แล้ว

    If b is terminating symbol then 2 and 3 can also be the final states

  • @Rajveer__singhhhh
    @Rajveer__singhhhh 11 หลายเดือนก่อน

    Really helpful

  • @AadeshingaleOfficial-zl5fd
    @AadeshingaleOfficial-zl5fd 3 หลายเดือนก่อน

    Nice Sir 😊

  • @apporvaarya
    @apporvaarya 5 ปีที่แล้ว +2

    Good tutorial :)

  • @fbng
    @fbng 4 ปีที่แล้ว +1

    You joined the (a+b) part of the FSM to S1, why cant you cojoin that section to S2 instead, surely it makes more sense, since at S1 , you have three A inputs, but at S2 you would only have only 1 A input and 1 B input . thanks

  • @uditnarayan8645
    @uditnarayan8645 2 ปีที่แล้ว +2

    how did you know there are two final state

  • @PetBuddies
    @PetBuddies 2 ปีที่แล้ว

    given regular expression convert it to DFA via Epsilon-NFA

  • @federicobruno2378
    @federicobruno2378 6 ปีที่แล้ว +1

    You're the best one.

  • @hilih_ism
    @hilih_ism ปีที่แล้ว

    shouldn't state 5 be final? to satisfy the positive closure of a

    • @abhivk5176
      @abhivk5176 ปีที่แล้ว

      it cant be! it needs b also to get to the final state right!

  • @andersonlontsi299
    @andersonlontsi299 4 หลายเดือนก่อน

    wonderful

  • @pankajkalania5
    @pankajkalania5 7 ปีที่แล้ว

    Please make a video on "Dc equivalent circuit of CE BJT Amplifier".

  • @NadaALbahri95
    @NadaALbahri95 7 ปีที่แล้ว

    what do you mean by finite automata NFA OR DFA?

    • @nixokol
      @nixokol 7 ปีที่แล้ว +2

      NFA = Non-Deterministic Finite Automaton
      DFA = Deterministic Finite Automaton
      In this case he made a NFA as he said in the video. One big difference between a NFA and a DFA is that the NFA can have multiple states caused by the same input. This example you can see when he makes input "a and b" cause a loop in state 1, but "a" can also go to state 5 which leads to another end state.

    • @shashikalaraju5769
      @shashikalaraju5769 3 ปีที่แล้ว

      Can be anything

  • @satyakibose8402
    @satyakibose8402 7 ปีที่แล้ว +4

    Can we make the state 4 only final state??

    • @beeplove7032
      @beeplove7032 7 ปีที่แล้ว +1

      i think we can if we if we connect the state 5 with 4 directly by having the input as b

    • @ChristianBurnsShafer
      @ChristianBurnsShafer 6 ปีที่แล้ว

      Yes, connect state 5 to state 4 using input b. Doesn't really matter; it is non-deterministic anyways.

    • @Ankitkumar-vn7mu
      @Ankitkumar-vn7mu 6 ปีที่แล้ว

      yes, you are right

  • @AyanKhan-fe4qc
    @AyanKhan-fe4qc 3 ปีที่แล้ว

    Union and terminating symbol is same???

  • @leonh2140
    @leonh2140 ปีที่แล้ว

    amazing, thanks!

  • @rajatrawat4986
    @rajatrawat4986 7 ปีที่แล้ว +1

    nice share please upload more like these

  • @swm7f137
    @swm7f137 7 ปีที่แล้ว +1

    please upload more talk about CFG

  • @ABugWithTheBigDreams
    @ABugWithTheBigDreams 4 ปีที่แล้ว

    On input B we should reach to the Final St

  • @allahs_creation233
    @allahs_creation233 ปีที่แล้ว

    which app you use on your laptop to write like this? someone know tell

  • @Ravi-he6yl
    @Ravi-he6yl 6 ปีที่แล้ว

    State 1 will also be the final stage so it can accept (a|b)*....but in video it is not ....then how could it be accepted??.

  • @shashanksharma8229
    @shashanksharma8229 7 ปีที่แล้ว +1

    sir kindly upload more videos on CFG and CNF an GNF

  • @ravikant-pal
    @ravikant-pal 7 ปีที่แล้ว +1

    sir plz upload the lecturers of regular grammar

  • @rajeshkumawat1476
    @rajeshkumawat1476 7 ปีที่แล้ว

    sir we are getting two final state but when compare to third example there is only one final state its same like this problem . if it is two final state is accepted then explain how???

  • @null3377
    @null3377 5 ปีที่แล้ว +1

    what if the second part of equations replaced by abb|a*b instead of abb|a^+b

    • @backslash8874
      @backslash8874 5 ปีที่แล้ว +2

      Transition from state-1 to state-5 would happen on getting "a,epsilon" instead of just "a" then...

    • @null3377
      @null3377 5 ปีที่แล้ว

      @@backslash8874 Oooh, right. Thanks so much! ^^

  • @ElifArslan-l9g
    @ElifArslan-l9g ปีที่แล้ว

    thank you

  • @ramprasadbhagat8072
    @ramprasadbhagat8072 5 ปีที่แล้ว +1

    Sir, i think something is wrong! As in the regular expression only 'b' accept but you have drawn NFA that does not accept 'b'.... I think the state 1 to 5 there is input b transition and 5 will be the final state. Sir, plz reply to my problem😃

  • @somalinetworksolution283
    @somalinetworksolution283 7 ปีที่แล้ว +1

    Sir, please upload more.

  • @varunvarun6022
    @varunvarun6022 7 ปีที่แล้ว

    Thnkuuu Sir.............

  • @RahulSikarwar99
    @RahulSikarwar99 7 ปีที่แล้ว +1

    Sir Please Upload Next Videos in the Playlist.. And Please let us know if there will be long delay.

  • @carlottafabris225
    @carlottafabris225 6 ปีที่แล้ว

    If I have the regular expession: (ab)* + (bc)* how would the automata be?
    Thank you!

    • @Naz-ei6be
      @Naz-ei6be 5 ปีที่แล้ว +2

      My guess is something like 3 states, state A as your initial and final state. State B where A--a-->B, B--b-->A, State C where A--b-->C, C--c-->A. Thats what I came up with but it seems to work, could be wrong? Since you have (ab)* and (bc)* the FSM should accept no input (as the closure operation can include epsilon) or some length of ab OR bc. (OR operator as there is a + in between)

    • @BlizZarDaSh
      @BlizZarDaSh 5 ปีที่แล้ว

      @@Naz-ei6be yea, this makes since, I don't think your wrong.

  • @riyakumarichoursia6692
    @riyakumarichoursia6692 5 ปีที่แล้ว +1

    Can we connect state 5 to state 4? Or we need to make two final states necessarily?

    • @darkludge
      @darkludge 3 ปีที่แล้ว

      Yh ig u can rt🤔

  • @trollbus6104
    @trollbus6104 3 ปีที่แล้ว

    How state 4 is final state

  • @EkarFCB
    @EkarFCB 7 ปีที่แล้ว

    Instead of having a separate final state 6, can 5 go to 4 with b instead ? Leaving with only 1 final state.

    • @kingzai1314
      @kingzai1314 7 ปีที่แล้ว +1

      yeah.. thats what i was thinking.. its possible.

  • @kmanish2528
    @kmanish2528 ปีที่แล้ว

    Instead of 4,6 we have have only 4 only right??

  • @dhanushsivajaya1356
    @dhanushsivajaya1356 4 ปีที่แล้ว

    Thankyou sir

  • @UdaySingh-zw3fs
    @UdaySingh-zw3fs 7 ปีที่แล้ว

    can anyone please tell why there are two final states ???

  • @kaan-3009
    @kaan-3009 4 ปีที่แล้ว

    is symbol U same with |

  • @friends4u380
    @friends4u380 7 ปีที่แล้ว +1

    sir please upload next topic pushdown automata

  • @jitendrapatel7896
    @jitendrapatel7896 5 ปีที่แล้ว

    Hello sir can you solve a(a+b)*bb this question?????

  • @frontend.made.eazzzy
    @frontend.made.eazzzy 6 ปีที่แล้ว +2

    we can make it using only 4 states make loop of 'a' just on state 2

    • @bharanivishwamitra
      @bharanivishwamitra 5 ปีที่แล้ว

      that might accept say, 'ab' as a string too.

    • @bestrongbegood2976
      @bestrongbegood2976 4 ปีที่แล้ว

      @@bharanivishwamitra this language accepts also 'ab' !

    • @bharanivishwamitra
      @bharanivishwamitra 3 ปีที่แล้ว

      @@bestrongbegood2976 Yeah, I took the wrong example. But I still feel like the proposed model could be wrong because the model rejects every input that starts with 'b' if the loop is just on 2nd state, but not all inputs with 'b' must be rejected. Instead the loop on state 1 should be unchanged but an additional loop only for 'a' must be created on state 2 to model it in 4 states.

  • @sahilsaxena8374
    @sahilsaxena8374 3 ปีที่แล้ว

    Sir if string="b"
    It will not accept by your solution

  • @pinakranjandas5770
    @pinakranjandas5770 2 ปีที่แล้ว

    this fa can be reduced to 3 states
    (initial state)----->A(self loop of a,b) then getting b goes to state B(final state) then getting b goes to state C(final state)
    it is accepting all the strings

  • @akshaykakad7479
    @akshaykakad7479 6 ปีที่แล้ว

    Convert the following regular expression into deterministic finite automata.
    (a+b)*abb(a+b)* please ...sir immediate solve this problem?

    • @geterewlij
      @geterewlij 5 ปีที่แล้ว

      its late but if anyone else was wondering: make 4 states, and make a self loop for for inputs (a,b) on the first and last states. then connect the four states using a, b, and b (in order). the last state is the accepting state.

  • @gorledivya6451
    @gorledivya6451 3 ปีที่แล้ว

    Why we consider 6 states

  • @traptigupta9371
    @traptigupta9371 7 ปีที่แล้ว +2

    why don't you use null moves after removing closure

  • @massoudshaker75
    @massoudshaker75 4 ปีที่แล้ว

    The Best

  • @ChAkIrLbR
    @ChAkIrLbR 5 ปีที่แล้ว +1

    1----a,b---->1 1------a----->2 2------a------->2 2-----b---->3 3-------b------->4 is that incorrect ? 3 and 4 are final states

    • @bharanivishwamitra
      @bharanivishwamitra 5 ปีที่แล้ว

      If this is the case, "ab" will also be accepted as a string.Which shouldn't be according to the given language.

    • @bharanivishwamitra
      @bharanivishwamitra 5 ปีที่แล้ว

      Instead, I think
      1----a,b---->1 1----a---->2 1----a---->3 2----b---->3 3----b---->(4)
      should work. 4 alone is final state.

  • @rohitpsr3910
    @rohitpsr3910 5 ปีที่แล้ว

    Sir can you make some more examples

  • @Ankit-we8ym
    @Ankit-we8ym 7 ปีที่แล้ว +1

    sir please make more tutorial thanks for this

  • @hammerguy123
    @hammerguy123 6 ปีที่แล้ว

    please reply to the comment section. we do have our doubts and want them to be cleared out.

  • @rajeshkumarponnala2519
    @rajeshkumarponnala2519 5 ปีที่แล้ว

    Can we give the last " b" from State 5 to 4

    • @BlizZarDaSh
      @BlizZarDaSh 5 ปีที่แล้ว

      Yes we can, that's also correct. There's never 1 finite automata for Regular expression.

  • @aayushbisht4307
    @aayushbisht4307 2 ปีที่แล้ว +2

    What if it was a* instead of a+

  • @foreverursabhi
    @foreverursabhi 3 ปีที่แล้ว

    How about a*b*?

  • @Sanjanaudemkadi
    @Sanjanaudemkadi 4 หลายเดือนก่อน

    It is not in DFA format