Greibach Normal Form & CFG to GNF Conversion

TOC: Greibach Normal Form & CFG to GNF Conversion
Topics discussed:
1) Greibach Normal Form
2) Steps to convert CFG to GNF
Contribute: www.nesoacademy...
Website ► www.nesoacademy...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...

[@Harsh-rm1tp]

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

[@ammu_00_7]

to pass the exams.

[@elotaco3426]

truee

[@thetechaholic1944]

To design compiler and programming languages

[@anjandey6089]

To impress your gf

[@AnjaliKumari-fy1uz]

@@anjandey6089 😂😂😂😂 exactly

[@siddharthverma1999]

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]

Thanks!!

[@vinayak186f3]

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]

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]

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).

[@khedubaba]

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.

[@ParnikaTutorials]

Yes I agee with Aditya

[@Likhita-h1l]

Ohh, Thank you🌹

[@mohammadnaseer5413]

Thank you

[@daljeetkaur3002]

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

[@krishna8655]

Are you a LPU student as well? 😂😂😂

[@sonasreedhar.1669]

My teacher also like thiss

[@User_435gyu6]

🤧that's so good

[@bitoffbalance4021]

Mr. Anand Bihari , loook at this😂😂

[@omerihtizaz9043]

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]

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]

@@kriskhandelwal6967 thanks bouiiiiii

[@clipfams8887]

@@kriskhandelwal6967 thanks

[@rishikrishsharma2654]

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]

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

[@yashrajsingh8700]

@@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]

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]

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

[@Likhita-h1l]

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

[@adarshpawar]

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]

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

[@vampyrkiller]

Right not left bro

[@bhaveshkandpal1706]

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

[@visheshupadhyay1774]

nice video

[@Ansari_Zubair]

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

[@voiceofyvr4006]

Congratulations for 1.5 million subs 🥳🤩

[@01Nullvoid]

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

[@rachitchhabra9578]

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

[@anuragroy11]

Same question!

[@kunaldeshpande6487]

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]

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

[@ritraina]

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]

exactly

[@AadityaChouhan]

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

[@giacomodovidio2871]

your lessons are powerful!

[@siddharth.chandani]

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

[@HighbrowDirector]

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

[@vaishnaviv2169]

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

[@HighbrowDirector]

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

[@vaishnaviv2169]

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

[@HighbrowDirector]

@@vaishnaviv2169 Actually no mistake 1 step was redundant

[@vardaanbajaj3181]

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?

[@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

[@jatinbansal4759]

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

[@NSTuts]

screen shot lele na pagal

[@nabhavlogs371]

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

[@clipfams8887]

same doubt

[@webtube4131]

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 )

[@kgCode658]

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

[@gopichandh5239]

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

[@HighbrowDirector]

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

[@sparkplug8763]

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.

[@sankalparora9261]

Thanks. Nicely explained.

[@mohamedkanu66]

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

[@GustavoFringe-dv2yg]

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

[@omop5922]

Videos were sufficient?

[@GustavoFringe-dv2yg]

@@omop5922 yes, more than sufficient

[@usamafiaz6964]

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

[@MohammadHassan-vd2zo]

good teaching

[@abanoubbenyamin1729]

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

[@gouravchatterjee7052]

it can be done in a simpler way also

[@poojadonode524]

How?????

[@chandreshwarikhanorkar6668]

Excellent Sir.. Thank you so much ...

[@tahreenshaik277]

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

[@vinayaksharma-ys3ip]

Thank You So much sir👍👍👍

[@saicharan823]

Great lecture . Impressed with it !!

[@imranshaik5325]

thanks

[@RA-CSEA-eh3es]

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

[@friendlyneighbourhood930]

Thank you, Sir.😊😇

[@MAX-rb2vh]

Why did we write A4 twice?

[@shubhammishra4122]

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

[@iyadhabdessalem3496]

thank you

[@KamalSingh-nv7nh]

Thank you sir👍

[@dennisthomas971]

Thank you❤🙏

[@ricaspinto]

sir*

[@kerteske3811]

I was searching for GNF - Polo G

[@shubhammishra4122]

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

[@shashirekha3021]

Amazing videos

[@merida3975]

still have many doubts

[@dhanushsivajaya1356]

Thankyou sir

[@NikhilS-1]

Here we go generational pain.

[@Rohit-qp1ye]

Good work sir keep going

[@vikrampareek8713]

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

[@gagaadadasdadadas]

thx man ! nice explaind !

[@ricaspinto]

Sir*

[@JustwaitNwatch-w]

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

[@bireshbiswas870]

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

[@junaidshaikh3597]

This example is wrongly solve d

[@RohitArtCraft]

Sir you are great but your voice is not perfect

[@ArifKhan-kp8zs]

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

[@amrabuodeh]

replace the valoo

[@ozgunozerk334]

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

[@adilbimzagh5453]

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

[@kakashi7943]

Wrong solution

[@Likhita-h1l]

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

[@saurabhjondhale]

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

[@Sortedarray32]

Dukh dard peeda kasta

[@smrpkrl]

3:04

[@RashmiSingh-rl5ge]

Could you go any slower😒

[@ManishSharma-lm3wg]

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

[@RashmiSingh-rl5ge]

Manish Sharma Fitness I was being sarcastic dude

[@bharanivishwamitra]

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

[@princekumaryadav6439]

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

[@eeshankhan4607]

A of 1 😂😂😂

[@_Yank_]

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

[@mohamedkanu66]

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

[@AhamedKabeer-wn1jb]

Thank you ..

[@ricaspinto]

sir*