Well, if you think about it in terms of generating a string “from the outside in”, with something inside generating to both sides, it’s easy to see what can be a CFL. For A, since opposite pairs of letters match, we must generate them at the same time: S -> aSa | bSb | eps For C, we know how to generate correlated pairs, so you can make 3 cases that generate 1, 3 or 5 b’s for each a: S -> T1 | T3 | T5 T1 -> aT1b | eps T3 -> aT3bbb | eps T5 -> aT5bbbbb | eps And D is a connected pair within a connected pair, so we can generate one and then switch to the other: S -> aSa | bSb | T T -> aTb | eps Figuring out if B isn’t a CFL is more complex.
We can't prove b is not CFL using word w = b^p a^p b^p b^p, because in case where v and y are a's and second b's we are always in L. The word w = a^p b^p a^p b^p a^p b^p works
its from easiest gate paper in 20years. better way to solve those are just push them into stack and try to pop to generate another part of string if u can its context free if u cant its not context simple wwr is easy to see as u can push all simbols while generating w and then pop all to generate wr. same with wanbnwr. u can push w then x n times then keep poping x to generate bn then pop w to generate wr.
Not a good explanation. Doesn't actually show us what pumping them up or down looks like if applied. Just says they would inherently leave the language and break the lemma if pumped either direction which is the same thing as telling a 5 year old the car goes fast because of hydraulic compression system without actually showing them how it works. You need to actually show and break down exactly why your claims are valid instead of just making a bunch of huge broad claims and not backing them up with clear examples.
Next video! How many DFAs with 3 states and one input character are possible? ua-cam.com/video/R9C9YiMNrFE/v-deo.html
Well, if you think about it in terms of generating a string “from the outside in”, with something inside generating to both sides, it’s easy to see what can be a CFL.
For A, since opposite pairs of letters match, we must generate them at the same time:
S -> aSa | bSb | eps
For C, we know how to generate correlated pairs, so you can make 3 cases that generate 1, 3 or 5 b’s for each a:
S -> T1 | T3 | T5
T1 -> aT1b | eps
T3 -> aT3bbb | eps
T5 -> aT5bbbbb | eps
And D is a connected pair within a connected pair, so we can generate one and then switch to the other:
S -> aSa | bSb | T
T -> aTb | eps
Figuring out if B isn’t a CFL is more complex.
We can't prove b is not CFL using word w = b^p a^p b^p b^p, because in case where v and y are a's and second b's we are always in L. The word w = a^p b^p a^p b^p a^p b^p works
its from easiest gate paper in 20years.
better way to solve those are just push them into stack and try to pop to generate another part of string if u can its context free if u cant its not context simple
wwr is easy to see as u can push all simbols while generating w and then pop all to generate wr.
same with wanbnwr.
u can push w then x n times then keep poping x to generate bn then pop w to generate wr.
You deserve a huge credit!
nice one
Thanks that was very interresting thanks
palindrome is obviously context free
since we are pumping v and x
from s = uvwxy
if v = first string
x = reversed string
its obviously a palidrome
Not a good explanation. Doesn't actually show us what pumping them up or down looks like if applied. Just says they would inherently leave the language and break the lemma if pumped either direction which is the same thing as telling a 5 year old the car goes fast because of hydraulic compression system without actually showing them how it works. You need to actually show and break down exactly why your claims are valid instead of just making a bunch of huge broad claims and not backing them up with clear examples.