Greibach Normal Form & CFG to GNF Conversion
HTML-код
- Опубликовано: 15 июн 2017
- TOC: Greibach Normal Form & CFG to GNF Conversion
Topics discussed:
1) Greibach Normal Form
2) Steps to convert CFG to GNF
Contribute: www.nesoacademy.org/donate
Website ► www.nesoacademy.org/
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...
![Eminem - The Death of Slim Shady [Album Trailer]](http://i.ytimg.com/vi/X0HIrS6kUYI/mqdefault.jpg)
only god knows where I'll be using this in my life...
to pass the exams.
truee
To design compiler and programming languages
To impress your gf
@@anjandey6089 😂😂😂😂 exactly
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!
Thanks!!
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
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
Oh my god, my teacher makes notes from your videos and teach us by that notes😂😂
Are you a LPU student as well? 😂😂😂
My teacher also like thiss
🤧that's so good
Mr. Anand Bihari , loook at this😂😂
your lessons are powerful!
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).
Congratulations for 1.5 million subs 🥳🤩
M fan of the way you teach...thanks a lot..big thumbs up👍
nice video
Excellent Sir.. Thank you so much ...
Thanks. Nicely explained.
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.
Yes I agee with Aditya
Ohh, Thank you🌹
Here 5:00 you solve my doubt.. Thanks sir
Great lecture . Impressed with it !!
Nice video sir... completely able to understand the concept...☺️☺️
Thank you, Sir.😊😇
good teaching
Thank You So much sir👍👍👍
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
Why should do Step 1,when we know that in CNF these Step Have to do.We should do directly step 2.
Thank you sir👍
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
Yes it's right can can you explain me why did this happen in this example.please response me if you know
@@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.
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
Amazing videos
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
thanks
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'.
Yeah I agree. The expression was still not fully converted into a CNF.
Right not left bro
thank you
Aren't we going to add S'-> S???
thx man ! nice explaind !
Sir*
Thankyou sir
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?
Thank you❤🙏
sir*
Good work sir keep going
please upload videos on pda and turing machine .i have my exam on 20 june
Thank you ..
sir*
not in CNF form as S is in the right hand side
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
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
@@kriskhandelwal6967 thanks bouiiiiii
@@kriskhandelwal6967 thanks
it will be really helpful if you provide the image of the things you tought over here
screen shot lele na pagal
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 )
But, At 3:54 according to CNF the starting symbol shouldn't be on RHS of any production rule...😢
Excuse me sir! 3:50
here there S on right side of production. And how it is already in CNF??
B-->SB. Here it is not in Chomsky Normal Form since S is on the right side. Please explain!!?
Same question!
rachit chhabra no buddy S is right side still it is non terminal because it's a starring point....... Generally it's non terminal
Yes, we would have to add the production S' -> S. Small oversight.
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
exactly
A4-->b A3 A4? is this possible?
same doubt
I was searching for GNF - Polo G
Is there any Solution Manual for Automata By cohen and denial ?
it can be done in a simpler way also
How?????
Sir i have my examss from 6th of july . It would be very helpful if you put now.
I think you forgot to change 'A3' to 'a'.
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.
In step 4 what if it had....(A4->A4|A3)?
Why did we write A4 twice?
Doesn't BB in S makes it not in CNF because BB is repeated
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
still have many doubts
Since we are already removing Unit Productions and Null Productions in CNF, Why do we need step 1 here?
The step which he said in the first, is for the conversion from CFG to GNF and not CNF to GNF.
@@vaishnaviv2169 If its already a CNF there will be no Null productions and Unit productions.
@@HighbrowDirector yeah... So, did he remove some unit or null values bymistake?
Or is there any mistake in that video?
@@vaishnaviv2169 Actually no mistake 1 step was redundant
tomorrow is TOC exam,,, Wish me luck guys😥
Videos were sufficient?
@@omop5922 yes, more than sufficient
This example is wrongly solve d
Sir i need to learn whole turning machine . How much to pay you to get it?
wrong!! As B->SB has S on right side. it is not in CNF!! Please do convert it
replace the valoo
Here we go generational pain.
its not gridback, its gribah (i pronounced like "i")
:))))))))
it's not gribah eather ! the therm "ch" has its own prononciation !
3:04
Sir you are great but your voice is not perfect
Dukh dard peeda kasta
A of 1 😂😂😂
it should be A4--> b | A2 A3 A4 | A4 A4 not A4--> b | A2 A3 A4 | A4 A4 A4
Wrong solution
What's the wrong solution?
May I know??
ab exam ho gaya ab kya dal rahe hoo. 😨😨ye questions exam me v aya tha
Could you go any slower😒
Sorry to interrupt but he is already slow,
Or watch at *.75 speed 😂
Manish Sharma Fitness I was being sarcastic dude
@@ManishSharma-lm3wg Can you be any dumber, oof!
I beleive that this subject is the most useless subject in the world
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
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