Conversion of CFG to Chomsky Normal Form
HTML-код
- Опубликовано: 1 окт 2024
- TOC: Conversion of CFG to Chomsky Normal Form
This Lecture shows how to convert a Context Free Grammar to Chomsky Normal Form.
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 - ...
I just wanna say that I've spent my afternoon with your videos and I think I learned more in these couple of hours than I did for the whole semester... The way you teach is simply amazing. Thank you and greetings from Germany!
Same here as well from Malaysia!
Exactly! In one night I have learned and understood all the things that I couldn't understand during the semester. And I have passed the exam :)
same here, from India
You are from germany?
Same Bangladesh
This Academy is litrelly saving lives of many students 😭...
All I wanna do is Thank You🙏
Thank you, is not enough :)
Well appreciated
At 1:27, the first step S'->S doesn't conform to chomsky normal form, since S is not in T. But disappear in step 3.
I have been following this channel past two years. All I want to say is thank you so much for guiding me through various subjects. I have scored really well in whatever subjects you've taught me!!!
yours lecture really helps me to understand theory of automation
plz upload all remaining videos which is about PDA and turing machine
plz upload alls
BCOZ MY paper coming soon
please understand problem
thanks for giving me a such lecture to understand CNF
yes sir I agree Prince
yes true....we are waiting for those of turing Machine
actually we can't wait
ya plz my xams are coming plz upload them fast and thanx for teaching in such a great way....
Please treat teacher as Sir, sir. I dont understand problem
Please upload the rest of the videos asap.You are doing a huge service to mankind by making these videos.
i have no words for the way you explain a topic .... its like learning from the topic itself... great respect whoever you are
What Should we do if there is no S on RHS?????
Very helpful, these lectures are getting me through my theory of computation class.
Saaaame!!!
@@YuNgHaSaN same
@evanlecarde281 Same
I found the same question which is in my exam thank you!
😂
I jus came from a video of sonmeone who had no clue what they were saying
Thank you so much for this great explanation , understood fully.
Sir I have a question. In the second step there is we have to remove the null production..but in the grammar there is only B tens to epsilon..there is no A tending to epsilon..from where you got that grammar ..I couldn't get that part
because he remove B from A so there remain null.
I have seen almost every lecture of toc Its very helpful for learning and getting understand to toc topics this is the best channel of RUclips for studying toc I explore many channel and waste the time but you neso academy you are the best
Null production removal method in previous video is different from this one. Please tell which one is correct and should be followed.
Both are same, in this lecture the concepts of removal were directly put into action.
Sir in this question A not belongs to € still you wrote A give to €
if you look closely you'll notice that in P: S -> ASA | aB , A -> B | S , B -> b | €
its A -> B and B -> €
now here it can be understood as A -> B -> €
or in other words A -> € and B -> €
In final step 4 and Step 5, We add "X" instead of "SA" and "Y" instead of "a" rite...., Then why not we write the production rule like this- S-AX / YB / X / AS / Y.... ?
sir,(S->AX/aB/a/AS/SA) why the last SA is not replced by X ?
There are no words describe a devotional thank fullness for your work🥺🙇♀️🫶
but you didn't even put the link of the previous video.... bruhh
In step 4,can we replace the most right sided SA with X????
No, then you'll have only one Non terminal symbol, which is not in CNF.
I know this comment is kinda late )
Sir plz provide the lectures on PDA and TURING MACHINES🙏
how A-> epsilon is there?
Yes exactly what I was talking about!!
epsilon is hidden there, so there should also be one S' and S as well, im not sure why those haven't been mentioned either
You are born to teach.
Right, now i can sleep peacefully
Sir please upload remaining lectures. I'm totally dependant on your lectures. My exams starts from 12 May. Because of you I was able to pass DLD in last semester. All the students are waiting for your lectures. Please it's a sincere request upload it ASAP!
Bhai job lag gayi kya?
@@Arham__Qasim haan ji bhai, job lag gyi hai
@@abhishekbalyan7189 congrats🥳
2022.. and students still follow these videos .
Sir,In the removing unit production of S'->S at 7:17
You've replaced S' by the value of S but in the lecture of removing unit productions you have stated that you have to replace A->B by A->x whenever B->x in the Grammer and x belongs to terminals, but Here in S'->S ,S contains both terminals and non terminals
ya i think it should be S'->a because on replacing S'->S , S->a so S'->a . am I correct or not ??
Same confusion!!!! if anybody can explain please do so!
@JAY prakash sorry to say but u are wrong, think if S' wants to go to another option or a non terminal Symbol like AS but in your case you are restricting S' to go only to a terminal symbol a.
@snehal machan Go step by step , first add S'->S (coz S is on the right hand side) then it becomes a case of unit production and after that remove the unit production and also remove more than 2 non terminals.
ya exactly i was wrong . now i have understood .thanx
wow it was great to extract the concept from your videos . hope to see yuh in the upcomming days with new more conceptual videos . thanking you from NEPAL............
Why a is a null production?
Hi! I wanted to ask what should you do if you have:
A--> SbS ?? how can you transform it to CNF?
Thanks in advance :)
A->XS
X->SY
Y->b
Bhai video to daal do aage ki.. Yahaan exams shuru hone wale hai mere. Fail karaoge kya. Bachche ki ijaat bacha lo.
you have to pay for further videos otherwise wait .................
hahahahahaha really iam even ready for that atleast it is very much better than my college my college teacher knows nothing about automata
Vyom Mishra
How was the exam bro ?
I am not able to understand what is the use of introducing new S ' . In the solution its looking redundant.
at 10:45 - why let X -> SA and not say X-> AS ?
When we convert a given CFG to CNF. The following simplification order must be followed strictly:
1. Elimination of Null Productions (Epsilon Productions)
2. Elimination of Unit Productions
3. Elimination of useless Symbols (useless Productions)
Then the remaining process will be very Easier.
Thank you so much for this video❤️❤️it's very helpful for mah MSc exams😘😘
Sir canyou plz upload video on PDA , PDA to CFG conversion ,CFG to PDA conversion and TURING Machine
Please assist:
Convert the following CFG to Chomsky Normal Form (CNF):
S → bXbZ | aXaY
X → baY | abZ | Λ
Y → aaX
Z → bbX | Λ
at 10:46 we took x->SA not x->AS as AS was also common of the three. Any specific reason?
just a matter of preference nothing else.
But S` is an useless production. Can't we just eliminate that?
yeah its redundant
🥺❤️
If S=aAD , A=aB/bAB , B=b , D=d
Then step 5 will give
S=XAD, A=XB /YAB ,D=d,X=a,Y=b
Which is not CNF
Please anyone clear this
I don't understand why we removed the S->S rule. I know it's useless but I can't seem get to the solution that removes this production rule and I'm afraid that I'm going to miss the omission of an important rule in the future.
403 am thanx
The level of questions this Channel uses is absolutely great..
I have seen many videos of this topic but the question they take were very basic.. which obviously didn't clear whole concept..
I swear to God.......indians have carried the whole computer science field on their backs
sir we are glad enoughfor this fav effort u done for us .............
we are eagerly waiting for ur further lectures
11.29 if you replace a with y then y don't replace single a with y
Easily the best video on this method, thanks
I think starting symbol 'S' should not be appear on the right-hand side of any production ?
What do we make S' for? It is not accessible at any point if we start from S, thus it's a useless production
pls upload the videos of PDA and turing machine and thanks for such an excellent videos
it will definitely help me in exams.....
Hi sir, please upload remaining lectures about PDA and Turing machines. the way you explaining is in simple manner understandable. waiting for your next videos
neso bhai saare subjects ke videos daalo. mai vit mai hu humare college mai sare bacche neso se hi padhte hai. please aur bhi subjects daalo. vit mai pata karo aur konse subjects hai unki bhi video daalo.
Has anyone noticed this? At the end of the conversion, the last term for S, S` and A is SA which was equated to X in a previous step. So shouldn't we simply write X there too? Can anyone answer that?
The definition of Chomsky Normal form says that the right side can have either a single terminal or two non-terminals.Since X is a single non-terminal it cant be put in the place of SA.
prasanth thanks for explanation. I understand it now.
Unit production removal is still not done completely na as A still contain ASA|aB etc
sir please add push down automata lectures also it will be really helpful and appreciable .........great work..
sir please upload the remaining videos as soon as possible..please
🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏
Johnson Cynthia Jones George Williams George
At the last step can we replace the S -> aB with S -> SB ??
we have a production of S -> a...so we can replace that a with S...right?
thank u so much for this videos
Thank you for teaching with wonderful dedication 🇮🇳
Cristal clear explanation sir💀.. thank you soo much.. ur vedios r our all time saviours.
Well that was really helpful , I really appreciate your work Sir. Greetings from Pakistan🇵🇰🇵🇰
Why we have introduced S' -> S
Isn't it more of a useless production. What's the logic behind introducing such production?
Exactly! Even if we add it, why didn't he remove it at the end. Its common math, if you add any variable yourself, in the end you need to remove it.
In CNF, there's one more production rule(P): The start state doesn't appear on the right side of P. So, we changed the start state to S' so that it won't appear on right.
@@chahatjindal9455 😂
@@jahnavibhardwaj3320 why chomsky made this ( s' - > s) wast production
Thank you for these videos sir.
plz upload rest of the topic videos which are turing machine, push down automata etc soon. It'll be really helpful for us.
Thank you so much for this great help.
Brown Sharon White Jeffrey Jones Jessica
Lee Margaret Clark Betty Taylor Joseph
Sir what is the need of first step if we do not take it then what will happen
sir when will u upload all the remaining videos exams are coming near.. pls upload soon. .. I will be very thankful to u sir
Why did AA didn't come
Thanks buddy for this its helpful for my internals
Sir please make the videos on Computer organizations and architecture 🤗🤗
ruclips.net/p/PLBlnK6fEyqRgLLlzdgiTUKULKJPYc0A4q
@@nesoacademy sir but this is not in detailed as per our college syllabus can you please refer that 🙏🙏🙏.
Thank you that's all i can say 🙌🏻❤️
at 7:37, S'->a (only this should have happened) because S->a; here 'a' is the only terminal and only the terminals and null are replaced in unit productions as told *in video 76 at 1:18*.
Also change on removing A->S
So, the result on removing all unit productions should be :-
S' -> a, S -> ASA | aB | a | AS | SA, A -> b | a, B -> b
sir pls upload more and more videos on this subject as early as possible
I am completely dependent on your videos
my syllabus for this paper is upto turing
machine
pls help me
Very well explained..Thank you Sir..
I think somewhat wrong in that sir..bec u only told that Greibach normalform is in the form of A->a,A->aC1C2C3......but in above video last ans is not in GNF form
sir in the last as the S and S' are same so can we combine them
In this step useless production is eliminated or not
But in your answer S is present on RHS side is it correct?
sir pls upload all remaining videos.......its very helpful for us.
here in step 2 there is no null production in A so why u put ebsilon nd then why u remove it?
I just want to know why are we doing this? Why are we converting it to Chomsky Normal Form? Does it offer any benefits compared to CFG?
again superb work thankyou! (India)
s is a start symbol but can i say it is a variable also?
anyone who can direct me to grammars and parsing
ur lectures are outstanding..plz upload cnf to gnf conversion quickly
if it possible plz upload pushdown automata.
If there are two terminals on right side like S->AX/YB/ac..then how consider for those terminals
We need consider like Y->a and Z->c
Then production will be S->AX/YB/YZ is it correct?
Awesome lecture sir ..... Thank you
In 11:52, you said that Y=a, then you have to change all 'a' production into 'Y'... But if u r doing so.. Then each production you have a add 'Y' individual(S'=Y, S=Y & A=Y) . Which can't possible...
Thank You So Much 💖
Sir in removing A->S at 8:25
You replace S with it's sting but after that A again start refer to B (A->B) but you does not replace B with b(smal b(terminal)) in end why? Please answer
Where do you have A->B? You have A->b, A->ASA, A->aB, A->a, A->AS, A->SA but never A refering B alone, you have to replace when you are refering to a single non terminal simbol, like in S'->S and A->B and A->S
why S->e is not a null production?
since A->e and S->ASA.......so S->e will occur though after infinite replacement of S on the RHS by SAS...
please clarify someone.
Thank you Sir ❤
Sir how you removed B->b/€ directly to get B->b there is no capital B on the right side how you removed it?
Please ,please🙏🙏
please complete the Theory of Computation course.Please upload videos of rest of the topics and their examples i.e., PDA and Turing machine
I have semester exams from 2nd week of next month.
Please upload.
NESO ACADEMY has helped me a lot in getting good marks in my previous semester.
Please help.
Isn't this the same example from the book "Introduction to the theory of computation" by Michael Sipser?
Great explanations in a simple way. Thanks