Greibach Normal Form & CFG to GNF Conversion

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

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

  • @Harsh-rm1tp
    @Harsh-rm1tp 5 ปีที่แล้ว +1074

    only god knows where I'll be using this in my life...

    • @ammu_00_7
      @ammu_00_7 4 ปีที่แล้ว +146

      to pass the exams.

    • @elotaco3426
      @elotaco3426 4 ปีที่แล้ว +10

      truee

    • @thetechaholic1944
      @thetechaholic1944 4 ปีที่แล้ว +98

      To design compiler and programming languages

    • @anjandey6089
      @anjandey6089 4 ปีที่แล้ว +122

      To impress your gf

    • @AnjaliKumari-fy1uz
      @AnjaliKumari-fy1uz 4 ปีที่แล้ว +12

      @@anjandey6089 😂😂😂😂 exactly

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

    For the ones having a doubt on "B -> SB": the example considered is already in the CNF, so there is no need to follow the "STEPS" in order to convert it to the CNF (thereby not following the S' rule). Hope this helps!

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

      Thanks!!

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

      In formal language theory, a context-free grammar, G, is said to be in Chomsky normal form (first described by Noam Chomsky)[1] if all of its production rules are of the form:[citation needed]
      A → BC, orA → a, orS → ε,
      where A, B, and C are nonterminal symbols, the letter a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is in L(G), the language produced by the context-free grammar G.[2]:92-93,106
      Source -wiki

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

      This subject is over for me nowwwww and i am not gonna see this shit again. I m so happy goodbye theory of computation 🗡 u were a bitch

  • @prathyushsunny
    @prathyushsunny 4 ปีที่แล้ว +22

    I recommend you people watch the previous videos on removing unit, null productions along with CFG to CNF conversion. Because steps 1 & 2, which take up majority of the process, aren't being applied to this example(which is a simple one).

  • @daljeetkaur3002
    @daljeetkaur3002 4 ปีที่แล้ว +76

    Oh my god, my teacher makes notes from your videos and teach us by that notes😂😂

    • @krishna8655
      @krishna8655 4 ปีที่แล้ว +6

      Are you a LPU student as well? 😂😂😂

    • @sonasreedhar.1669
      @sonasreedhar.1669 3 ปีที่แล้ว +4

      My teacher also like thiss

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

      🤧that's so good

    • @bitoffbalance4021
      @bitoffbalance4021 8 หลายเดือนก่อน +1

      Mr. Anand Bihari , loook at this😂😂

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

    Those who have doubt of S on RHS thus no CNF.
    So, you check for this(ie: step 1 of converting cfg to cnf as per previous video) when given production is not CNF. That is we begin with the procedure if given production is not in CNF form. But here given production is already CNF. Thus we don't follow those steps and it doesn't matter if S is on right side because its already in CNF form.

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

    your lessons are powerful!

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

    Congratulations for 1.5 million subs 🥳🤩

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

    M fan of the way you teach...thanks a lot..big thumbs up👍

  • @rachitchhabra9578
    @rachitchhabra9578 7 ปีที่แล้ว +39

    B-->SB. Here it is not in Chomsky Normal Form since S is on the right side. Please explain!!?

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

      Same question!

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

      rachit chhabra no buddy S is right side still it is non terminal because it's a starring point....... Generally it's non terminal

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

      Yes, we would have to add the production S' -> S. Small oversight.

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

      u r asking a right question but d thing after removing unit production s'-s the s' will be extended with what s has now

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

      exactly

  • @adarshpawar
    @adarshpawar 6 ปีที่แล้ว +20

    Why didn't we convert S'-> S? Because according to be in Chomsky Normal Form when S is in left side so we take S'.

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

      Yeah I agree. The expression was still not fully converted into a CNF.

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

      Right not left bro

  • @siddharth.chandani
    @siddharth.chandani ปีที่แล้ว +1

    Here 5:00 you solve my doubt.. Thanks sir

  • @rishikrishsharma2654
    @rishikrishsharma2654 7 ปีที่แล้ว +35

    In the CNF lecture you said that Start Symbol S must not be on Right hand side and inn this lecture S is in RHS than you also considered it as CNF

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

      Yes it's right can can you explain me why did this happen in this example.please response me if you know

    • @yashrajsingh8700
      @yashrajsingh8700 4 ปีที่แล้ว +18

      @@nikhilsharma8350 If you see in previous example it was A->S and in this it is B->SB. Hence alone if S is found then we have to change.

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

      I think there is a mistake as discussed in CNF S->ASB and A->S due to which we took a new production here too there is a state B->SB

  • @Nomnomnom165
    @Nomnomnom165 ปีที่แล้ว +13

    The steps are clear to me, thanks for the video. But i have one doubt. If it is already in Chomsky Normal Form, doesn't that mean that unit and null productions are already removed? And if so, is it fine to just check if it's in Chomsky Normal Form directly?
    Please correct me if I made some error

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

    Why should do Step 1,when we know that in CNF these Step Have to do.We should do directly step 2.

  • @Likhita-h1l
    @Likhita-h1l 8 หลายเดือนก่อน +5

    Aren't we going to add S'-> S???

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

    But, At 3:54 according to CNF the starting symbol shouldn't be on RHS of any production rule...😢

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

    You said that when i -> j , i < j not i >= j
    however when we see A4 -> b | b A3 A4 | A4 A4 A4
    you say that the part b A3 A4 is in normal form however here i == j

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

      it started with a non terminal symbol that's why it was accepted
      if it would have been A3bA4 then we would have to replace the A3
      but since it started with b it was accepted

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

      @@kriskhandelwal6967 thanks bouiiiiii

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

      @@kriskhandelwal6967 thanks

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

    Excuse me sir! 3:50
    here there S on right side of production. And how it is already in CNF??

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

    A4-->b A3 A4? is this possible?

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

    Thanks. Nicely explained.

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

    Since we are already removing Unit Productions and Null Productions in CNF, Why do we need step 1 here?

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

      The step which he said in the first, is for the conversion from CFG to GNF and not CNF to GNF.

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

      @@vaishnaviv2169 If its already a CNF there will be no Null productions and Unit productions.

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

      @@HighbrowDirector yeah... So, did he remove some unit or null values bymistake?
      Or is there any mistake in that video?

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

      @@vaishnaviv2169 Actually no mistake 1 step was redundant

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

    not in CNF form as S is in the right hand side

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

    Nice video sir... completely able to understand the concept...☺️☺️

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

    If i have a production of the form: A1 -> b A4 A3 A2 (A1, A2, A3, A4 are Non-terminals and b is a terminal), will this production be in GNF?

  • @vinayaksharma-ys3ip
    @vinayaksharma-ys3ip 3 ปีที่แล้ว

    Thank You So much sir👍👍👍

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

    it will be really helpful if you provide the image of the things you tought over here

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

      screen shot lele na pagal

  • @MohammadHassan-vd2zo
    @MohammadHassan-vd2zo 6 หลายเดือนก่อน

    good teaching

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

    Thank you, Sir.😊😇

  • @gouravchatterjee7052
    @gouravchatterjee7052 6 ปีที่แล้ว +4

    it can be done in a simpler way also

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

    Excellent Sir.. Thank you so much ...

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

    Great lecture . Impressed with it !!

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

    I think you forgot to change 'A3' to 'a'.

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

      no, that breaks the definition of GNF which is 'one terminal followed by n non-terminals'
      it's already in GNF so I guess the i < j part can be ignored.

  • @KamalSingh-nv7nh
    @KamalSingh-nv7nh 3 ปีที่แล้ว

    Thank you sir👍

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

    Sir urgent doubt hai........
    Diff. Method sai different answer aa sakta hai na?
    Bs condition satisfy Krna chaiye...
    Sir vo dusra method jismai A1,A2,A3 assume krte usse different aaraha

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

    Is there any Solution Manual for Automata By cohen and denial ?

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

    S occurred on the right side in the given example so it is not in CNF but how did you proceed further without converting it to CNF (please help I have exam tomorrow )

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

    Doesn't BB in S makes it not in CNF because BB is repeated

  • @RA-CSEA-eh3es
    @RA-CSEA-eh3es 3 ปีที่แล้ว

    In step 4 what if it had....(A4->A4|A3)?

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

    thanks

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

    Amazing videos

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

    Thank you❤🙏

  • @MAX-rb2vh
    @MAX-rb2vh 3 ปีที่แล้ว

    Why did we write A4 twice?

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

    please upload videos on pda and turing machine .i have my exam on 20 june

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

    thx man ! nice explaind !

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

      Sir*

    • @alexchandan9376
      @alexchandan9376 2 วันที่ผ่านมา

      Respect to your teacher please*

  • @GustavoFringe-dv2yg
    @GustavoFringe-dv2yg 2 ปีที่แล้ว +10

    tomorrow is TOC exam,,, Wish me luck guys😥

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

      Videos were sufficient?

    • @GustavoFringe-dv2yg
      @GustavoFringe-dv2yg 2 ปีที่แล้ว +1

      @@omop5922 yes, more than sufficient

  • @AhamedKabeer-wn1jb
    @AhamedKabeer-wn1jb 4 ปีที่แล้ว

    Thank you ..

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

    Thankyou sir

  • @Rohit-qp1ye
    @Rohit-qp1ye 5 ปีที่แล้ว

    Good work sir keep going

  • @foxdeveloper7707
    @foxdeveloper7707 19 วันที่ผ่านมา

    I think this helps :
    In the given grammar, 𝑆 S does not appear on the RHS directly (e.g., 𝑆 →…S…)

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

    MAny thanks for the good job. Please can you do a video on conversion of
    regular expression to context free grammar. Please help us as urgent as possible

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

    Here we go generational pain.

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

    still have many doubts

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

    I was searching for GNF - Polo G

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

    Sir i have my examss from 6th of july . It would be very helpful if you put now.

  • @NikitaNair
    @NikitaNair 25 วันที่ผ่านมา +1

    wowww

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

    wrong!! As B->SB has S on right side. it is not in CNF!! Please do convert it

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

    Sir i need to learn whole turning machine . How much to pay you to get it?

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

    This example is wrongly solve d

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

    3:04

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

    replace the valoo

  • @JustwaitNwatch-w
    @JustwaitNwatch-w 8 หลายเดือนก่อน +12

    I beleive that this subject is the most useless subject in the world

    • @bireshbiswas870
      @bireshbiswas870 2 หลายเดือนก่อน +2

      Without this we won't be able to write code. It's just that we don't know why we are studying all these, makes us cuss the sub. I can feel u broo

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

    Sir you are great but your voice is not perfect

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

    its not gridback, its gribah (i pronounced like "i")
    :))))))))

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

      it's not gribah eather ! the therm "ch" has its own prononciation !

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

    Dukh dard peeda kasta

  • @ArifKhan-kp8zs
    @ArifKhan-kp8zs 7 ปีที่แล้ว +8

    ab exam ho gaya ab kya dal rahe hoo. 😨😨ye questions exam me v aya tha

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

    it should be A4--> b | A2 A3 A4 | A4 A4 not A4--> b | A2 A3 A4 | A4 A4 A4

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

    Wrong solution

    • @Likhita-h1l
      @Likhita-h1l 7 หลายเดือนก่อน

      What's the wrong solution?
      May I know??

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

    A of 1 😂😂😂

  • @RashmiSingh-rl5ge
    @RashmiSingh-rl5ge 5 ปีที่แล้ว +4

    Could you go any slower😒

    • @ManishSharma-lm3wg
      @ManishSharma-lm3wg 5 ปีที่แล้ว +3

      Sorry to interrupt but he is already slow,
      Or watch at *.75 speed 😂

    • @RashmiSingh-rl5ge
      @RashmiSingh-rl5ge 5 ปีที่แล้ว

      Manish Sharma Fitness I was being sarcastic dude

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

      @@ManishSharma-lm3wg Can you be any dumber, oof!

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

      Dude I saw this lecture in 3x then it was at a formidable speed 😅

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

    bcoz of one small mistake u done in the whole que is gone wrong and my last 2h before the exam day gone to hell
    can u pls post another video in which u didn't do such type of silly mistake of S on the right side of CNF that u didn't recheck whether what u r teaching is right or not

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

    thank you

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

    MAny thanks for the good job. Please can you do a video on conversion of
    regular expression to context free grammar. Please help us as urgent as possible