Neso academy is only choice to learn all my subjects it is not only help to pass the exams ..it is also give a me best knowledge upon respected subjects....thank you so much 🙏
I had an insight about left recursion I would like to share: Let's say you have a left-recursive grammar T -> T + F | F and F -> 1. The partially expanded derivations / parse trees look like T, (T + F), ((T + F) + F), (...(T + F) + F) + F) ...), where the path from the 'T' root to the leftmost leaf is where the left recursion happens, or rather not to a leaf but to the point where T is replaced by some non-left-recursive production, i.e. the point were we use T -> F rather than T -> T + F. [Suggestion: draw or envision a diagram until this clicks for you.] Removing left recursion essentially means parsing that part of the tree in a bottom-up rather than top-down fashion. For example, let's rewrite my grammar to S -> F | FK and K -> + F | + F K and F -> 1 and let's derive 1 + 1 + 1. Note that S and K together replace T. So we go S -> FK -> 1K -> 1 + F K -> 1 + 1 K -> 1 + 1 + F -> 1 + 1 + 1. Whenever we add more factors (adding "+ F" ~ adding one more layer to the parse tree) we're always replacing the right-most non-terminal. But when we're expanding F, which is not part of the left recursion (except as an ultimate output as it were), we're replacing the left-most non-terminal. [Recall that left-most is top-down and right-most is bottom up: we see that the left-recursive part is handled bottom-up, but everything outside it can still be handled top-down]
Shouldn't we convert Z to A5 or something like that? in GNF we should have one Terminal followed by Non-Terminals lets say A in ascending order (or index) , but Z is not A?!
Can you do an explanation of how A4 -> b | b A3 A4 | A4 A4 A4 can be shown to be equivalent to A4 -> b | b A3 A4 | b Z | b A3 A4 Z where Z = A4 A4 Z | A4 A4?
Y'all, I'm stuck on this too and I wish he could've just explained it lol. How did he get "bZ" and "b A3 A4 Z"? Edit: Nvm, I think I figured it out. In the new production rule, "A4" can produce "b", "b A3 A4", "bZ", and "b A3 A4 Z". "bZ" is basically just "A4 A4 A4" but the first "A4" is replaced with "b" because "A4 -> b" ("A4" can produce the terminal "b"). The two "A4" which follow the first can be replaced with Z because Z -> A4 A4. The end result is "bZ" which was originally "A4 A4 A4". "b A3 A4 Z" is basically just "A4 A4 A4" but the first A4 is replaced with "b A3 A4" because "A4 -> "b A3 A4". The two "A4" which follow the first can also be replaced with Z like we have already done before so that the result of transforming "A4 A4 A4" is "b A3 A4 Z". "A4 A4 A4" = A4 (A4 -> b A3 A4) A4 A4 (Z -> A4 A4) = "b A3 A4 Z" I'm so sorry if my explanation is messy and informal but this is how I understood it.
Is this the actual way for solving left recursion? I think there is some other way for that. Then why are we solving it like this ..is it enough? I don't understand 🙁
Checking is done for Ai->Aj X.... Ai, Aj non terminal symbols. Not for Ai-> a(some terminal symbol) Aj. Only when right side of that production start with a non terminal which has i>=j
What if there is a case in left recursion where the problematic production lies in between the two variables. that is, here the problematic A4 lies in the beginning and the rest of them are easily changed with by adding Z after them but can there be a case when it lies in the middle, if yes then how to proceed with left recursion then.
The problematic variable should be the first one to appear on the RHS in the case of a left recursion. If it is some other variable, you can substitute it from the corresponding production and proceed, as this is not a case for a left recursion.
I'm from Ethiopia and I just want to let you know that your videos are a great help! Thank you!
Me : This question is easy.
Z : Let me introduce myself.
🤣
That Z is the fucking nightmare. 😭
I'm from NEPAL 🇳🇵🇳🇵 and I just want to let you know that your videos are very helpfull ! Thank you! sir❣
Who is watching this one day before the exams?
Me
Guilty! Just over 12 hours left...
@@nikhilmadhusudhanan7371 i did great buddy
1 hour before exam B-)
Me and probably my whole class. XD
Your lectures are miracleous. It will definitely help to understand things better as well as to pass the exams
Neso academy is the reason for passing my exams much impact compare to leaturea in college
Bro you get palced ??
tomorrow is my cat2 and this is the most helpful video i found on the internet.
I had some hopes and then i saw that Z production in the end i'am like Nop..
Same 😣
Me : This question is easy.
Z : Let me introduce myself.
Are you doing any job now ???
thank you so much for your efforts to explain the topic so lucidly!
thank you sir for the conclusion in such a short time.
Neso academy is only choice to learn all my subjects it is not only help to pass the exams ..it is also give a me best knowledge upon respected subjects....thank you so much 🙏
This is the easiest way I've watched whole in the TH-cam!
Why does it seem like normal forms are increasing the complexity more rather than reducing it......
lol
Thanks man for the video.
I can’t belive that I need to waste time learning this stuff during my master CS studies…
I'm from India ...ur videos is very helpful me ..in that lockdown..corona situation s
Thanks for the simplicity u use to make the concept clear😊
Thanks alot >. regards from the heart of Africa from Sudan .
Good and awesome teaching easily understand by everyone 👏👏and very clear for me👍
a big appaluse for ur hardwork dedication and simple,neat and clear explanation.thank u very much ..!!! ur every video really helped me a lot.
Thanks you so much Sir.....really all your hard work is being reflected through your videos👍👍💯💯💯
Thank You.
You saved my semester.
It's really helpful ❣️thanks neso academy 🙏
sir , u are amazing , thnx a lot for teaching TOC in such efficient manner
Having a quiz tomorrow, Thank you Neso academy for helping me out !
bhai same.
how did you perform in the quiz?
@@blitzkrieg7453 hhhh I passed the course, graduated 3 years ago and now working 😂
@@nicksbinarylife wow that’s great!
The cycle repeats.
Thank you so much sir!!! This was really helpful during exams🙏
I had an insight about left recursion I would like to share:
Let's say you have a left-recursive grammar T -> T + F | F and F -> 1.
The partially expanded derivations / parse trees look like T, (T + F), ((T + F) + F), (...(T + F) + F) + F) ...), where the path from the 'T' root to the leftmost leaf is where the left recursion happens, or rather not to a leaf but to the point where T is replaced by some non-left-recursive production, i.e. the point were we use T -> F rather than T -> T + F. [Suggestion: draw or envision a diagram until this clicks for you.]
Removing left recursion essentially means parsing that part of the tree in a bottom-up rather than top-down fashion.
For example, let's rewrite my grammar to S -> F | FK and K -> + F | + F K and F -> 1 and let's derive 1 + 1 + 1. Note that S and K together replace T.
So we go S -> FK -> 1K -> 1 + F K -> 1 + 1 K -> 1 + 1 + F -> 1 + 1 + 1.
Whenever we add more factors (adding "+ F" ~ adding one more layer to the parse tree) we're always replacing the right-most non-terminal. But when we're expanding F, which is not part of the left recursion (except as an ultimate output as it were), we're replacing the left-most non-terminal. [Recall that left-most is top-down and right-most is bottom up: we see that the left-recursive part is handled bottom-up, but everything outside it can still be handled top-down]
Thanks sir. I had doubts on this topic, now it's ok. Tomorrow is my exam. This topic is confusing on the book. Thanks again
I know this was written 6 months ago but same here lol,
mine is tomorrow too
@Swargam Hazarika i know this was written 2 weeks ago but i have my exam tomorrow too. LMAO!!!
@@amitthakur-ky9hq i know this was written 2 days ago but i too have my exam 2moro, #lol
@@dhairyaanchal8623 i know this was written 9 months ago but i have my exam tomorrow lmaaao🤣🤣
@@Mazino420 I know last comment was written 1 yr ago but I too have my exam tomorrow . LoL
4:32 shouldn't A3 also be removed since 4>3? It does not satisfy GNF conditions
Shouldn't we convert Z to A5 or something like that? in GNF we should have one Terminal followed by Non-Terminals lets say A in ascending order (or index) , but Z is not A?!
How about A3, shouldn't you replace it with a? as 3 is less than 4?
Thank you very much Neso Academy
.......very much greatful to you..
This looks incredibly complex, but the steps make it simple!
Dhanyawad Sirji❤❤❤❤❤
Thanks a lot sir, it was really helpful
you saved me !!!!!!!!!!!!!! Thank you
Plz upload vedios of pda n Turing machine ...
Got it at very first time.
Love from Nepal..
csit boards? hahaha
Sir dhuye Uda diye🥲🥲🥲
Can you do an explanation of how A4 -> b | b A3 A4 | A4 A4 A4 can be shown to be equivalent to A4 -> b | b A3 A4 | b Z | b A3 A4 Z
where Z = A4 A4 Z | A4 A4?
Can't find a decent explanation from the web, too.
Y'all, I'm stuck on this too and I wish he could've just explained it lol. How did he get "bZ" and "b A3 A4 Z"?
Edit: Nvm, I think I figured it out.
In the new production rule,
"A4" can produce "b", "b A3 A4", "bZ", and "b A3 A4 Z".
"bZ" is basically just "A4 A4 A4" but the first "A4" is replaced with "b" because "A4 -> b" ("A4" can produce the terminal "b").
The two "A4" which follow the first can be replaced with Z because
Z -> A4 A4. The end result is "bZ" which was originally "A4 A4 A4".
"b A3 A4 Z" is basically just "A4 A4 A4" but the first A4 is replaced with "b A3 A4" because
"A4 -> "b A3 A4". The two "A4" which follow the first can also be replaced with Z like we have already done before so that the result of transforming "A4 A4 A4" is "b A3 A4 Z".
"A4 A4 A4" = A4 (A4 -> b A3 A4) A4 A4 (Z -> A4 A4) = "b A3 A4 Z"
I'm so sorry if my explanation is messy and informal but this is how I understood it.
Thank you..sir I understood 👍👍
all the best for all your sem exams we will meet in future
In the last Z-> b(A3)(A4)(A4)Z should be "b(A3)(A4)Z(A4)Z"
By the way nice videos.
It is fine in the video and should remain the same
for those who have confusion in z... we are skipping 1st A4 and writing remaining A4's then Z..
Watching 2 hrs before the exams 👍👍💪
But, A2 -> b becomes a useless production?, since we have replaced all the values of A2 with b
can we remove A2->b ?
Is this the actual way for solving left recursion? I think there is some other way for that. Then why are we solving it like this ..is it enough? I don't understand 🙁
Sir, suppose if the production was A1-A4A4 then after creating z production what i write in new productiom A1?
Xouk
muthey.... nee life saveraaadaaa
Wonderful teaching
👌👌👌 explanation.grateful to uu.loved it
Thanks a lot sir for your clear explanation
Really very helpful!
Tis is life saving
Awesome tutorial sir
Watching this 30 minutes before the exam.
Thank u so much nesco academy
Awesome, thanks a lot!
Tq so much continue 🙏🙏🙏
My sir's explanation was pure shit..this video helped me a lot
sorry I have a question. for left recursion, the second product shouldn't be epsilon?
I mean: z -> A4A4Z | epsilon
but there can't be any null productions so when we remove it, the result will be the same shown in the video.
@@artifice_abhi yes thank you,after i saw the compiler design course, I understood that he does a epsilon reduction at the same time.
now how would you convert this to a simple grammar?
What is the use of CNF and GNF in real life
depends on what you do for a living
Makes parsing easy! Enables recursive descent parsing!
To pass in exam 😂😂
Thank you sir, I would like to know how to convert this CFG to GNF, can you please help me?
S -> A | S + A
A -> B | AB
B -> (S) | a | b | c
At 3:17 A4 is given three times but you have used only two times why along with Z anybody can tell
because only two are problematic as I >j and then i=j
where did bZ come from at 4:50
Thank you so much for this amazing explanation. Helped me loads.
if i
Off course but that form is not allowed in gnf
Thankyou 💗💗
Thanks
I have a doubt, you completely merged Z with A4 but didn't did the same with A1 and partially merged it?
Whats the point of converting them to increasing order when they aate to be replaced by some terminals
No simple explanation on yt than this
its b A3 A4 rater than b A3 A4 z they must have missed something if ur confused just remove z from eq , Thank you
Tysm sir very helpful
If this comes in uni exam, this better be worth atleast 30 marks!
4.18 why bZ?
I am watching on the day of examination
A4 -> bA3A4 is satisfy this form? 3< 4
check the definition of GNF it also says a terminal symbol followed by non terminals is in GNF
because we jst worry about first variable not 2nd and 3rd....;)
Isn't Z violating the rules? How is Z a part of A1, A2....An? Also, why is A4A4 allowed?
sir but in A4 -> b|bA3A4|bz|bA3A4Z A4> A3 i>j so is it right ? don't we have to make any changes
I have the same doubt. But I think once you get a terminal symbol in the beginning you don't need to check further
Checking is done for Ai->Aj X.... Ai, Aj non terminal symbols.
Not for Ai-> a(some terminal symbol) Aj.
Only when right side of that production start with a non terminal which has i>=j
LOVE
What if there is a case in left recursion where the problematic production lies in between the two variables.
that is, here the problematic A4 lies in the beginning and the rest of them are easily changed with by adding Z after them but can there be a case when it lies in the middle, if yes then how to proceed with left recursion then.
The problematic variable should be the first one to appear on the RHS in the case of a left recursion. If it is some other variable, you can substitute it from the corresponding production and proceed, as this is not a case for a left recursion.
I recommend www.csd.uwo.ca/~moreno/CS447/Lectures/Syntax.html/node8.html - The short story is that eliminating all "A_i → A_j α" productions where j
@@bluefog68 what if ...there would have been no variable after the problematic variable......then how are we supposed to write production rule for Z.
@@shaifaliverma153 then the production rule is trivial (A4 -> A4), and can be ignored in consideration, as its the identity rule.
@@bluefog68 oh ya...thanks!
This method is not working on other questions
nice explaination
sir why didn't you remove A3 as A3 < A4
Thank you!
Sir, Do we need to replace values of A1,A2,A3 that we assumed in the beginning after solving the problem???
good question, no need to replace it back
Awesome.....sir
شكراً لك
THANKYOU SIR
Don't we need to remove the A2->b production since it is useless at the end
any body tell me what is left recursion here ?
Tushar Verma when all the variables are same
@@prateeknatani9321 ok
A3-->A3A2A1 leads to left recursion when a variable refers itself
Can we replace A4 directly with 'b'?
nope
Thanks Sir...
Is it important to check for left recursion if we are going to convert CFG into CNF?
No Not !
Complex but good ...
step ending 4:21 seems strange
sir is turing machine is the upcoming topic??
sir plz upload control systems video lectures
I couldn't understand why we got bZ in A4
I know it's late but he discussed that part in his previous video on the very same topic.