TOC | Testing whether a language is regular or not | Ravindrababu Ravula | Free GATE CS Classes
ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- For Course Registration Visit: ravindrababura...
. For Any Queries, You can contact RBR on LinkedIn: / ravindrababu-ravula
Telegram: t.me/ravindrab...
Instagram: / ravindrababu_ravula_rbr
- GATE TOC Full Playlist: • Theory of Computation ... If you're considering studying abroad, don't forget to explore 'Games of Visas,' my dedicated consultancy service and TH-cam channel designed to streamline the process of studying abroad.
For Study Abroad, contact "Game of Visas" at 9494555454
15:03 repeated at 18:09 to 21:17
video has loop in it so it can be constructed with finite automata. The guy is not regular language but he is regular genious indian who teaches more than professors.
Thank you
@@selimmidikoglu5534 arey bhau tumhi ta uravar gheun rayale.
lmao@@selimmidikoglu5534
Something about Indian lecturers..... You just...learn!
The Ren my professor is indian and I don’t understand him. The TH-cam Indians must be from a different part of India 😂😂😂😂
Where u from
Not from all of them, there’s truth in that lol good Indian lecturers have saved my grades so many times
more like they are the only alternative in cs
There's a saying if u throw something out of window it will most probably fall on an engineer.. in India ppl first do engineering than descides what to do in future.. u will find indians not just in cs but all other branches of engineering although I'm from cs
What I learnt in 15 minutes is what I failed to grasp in 4 months of college...
+Indranil Dutta Lol, so true.
You didn't fail to grasp it Indranil, they failed to present it. I wonder why we have created this vicious cycle, go to college, pay high fees, learn nothing, watch youtube to pass their non sense exams. What do we eventually learn ?
Lol, that's true.
xactly my clg clases r just waste
I haven't learned to do all this in 3 monthes of college, but i learned it in 15 minutes with this video.
Sir, can you please explain pumping lemma too(it's important) ?
Thanks from Italy. Keep rocking.
Italiano come te, e non sono riuscito a capire in modo decente il pumping lemma andando a lezione tutti i santi giorni ._.
you can find pumping lemma in video number 63!!
@@prakarshpathak4070 And what about this Language?
L={wx^n | w is an arbitrary string containing x and y of length n} E={x,y} IS THIS LANGUAGE REGULAR OR NOT?
CAN SOMEONE WRITE ME ALL EXAMPLE, THANK YOU!!
@@ecommarrec w could be of infinite length and you have to store it in memory in order to write x^n. This implies that a finite automata representing this language cannot exist, therefore the language is not regular
ITALIA GOGOGOGGOO
This man just saved my life! It seems so complicated when you try to learn from reading the book...
I'm wasting my time going to university where the purpose of the teacher is only to fu
same goes for me.
..ck
could you please explain pumping lemma in context free languages
18:06 to 21:14 is a repetition of 15:00 to 18:06
So glad I'm pursuing my B.Tech after Jun 30, 2014!
I am wasting my time in college. This man is just genius!!! Thank you sir
got 2 hrs for xam... nd I'm watching ur videos !
Jhansi Pravallika fir to kuch ni ho skta bcz it needs practice a lot of practice
Aisa nahi hai.
Could you please explain the same for context free languages?
he is so good at this,now even people from other countries are also watching his videos
I like this man really . he's a genius . helped me with all of my courses . by all my heart thank you
one more doubt, for wxw^r | w,x belongs to (0+1)+
then regular expression shouldn't be like [0 (0+1)^+ 0 ]+ [1 (1+0)^+ 1] i.e instead of * we should use + while selecting x because x also belongs to a set of (0+1^+) ? Please correct me if I am wrong!
Exactly... in both 30:32 and 34:44 the * shd be replaced with +
For xww^R and for ww^Rx, can't we say language containing 00 and 11 as substrings? Why they are not regular sir?
in the last example at 36:15 min, for xww^r , why you are targeting for starting to be as 00 ,11 why not it could be 10,01 also,,and my second question is why two digit u r considering why not one,so its regualr expresion could be 1(0+1)^+ or 0(0+1)^+ ........why not this is possible ??
And in 34:52 it should be '+' right bcz x,w,y belongs to (0,1)^+ so it should have strings of length at least 4 they have used * it should be +
Then the set of all strings with substrings 00 and 11 would also contain languages that are not of the form xww(r)y. Someone please explain how having that as a substring doesn't involve including strings from other languages.
Nigga, you just saved my whole semester.
Yes and yes.
First, if you think that replying to an unknown man on the internet, and correcting his/hers morals/views is a good move, then I sympathize with you. Second, I know what it means and I have read about the African Americans more than you think I do. And, after everything that I have known about them, I don't think that a word makes much of an impact on the society; not in my country at least. On a side note, I would like to tell you that I refer to my friends as Niggas, not as a slur, but as a placeholder for their names. So, for me, this word has no meaning at all.
If you still think that you should reply, then please don't.
Kumar Chetan Abe chutiye nigga kisko bol Raha hai tu apni shakal dekha hai
Please add automatic subtitles i really want to understand all sentences
Sir have a confusion...why we need to check the last two symbols in case of XWW^r or,the first two symbols in case of WW^rY??
As if we consider inWXW^r...why cant we take the language as containing 00 or 11 as substrings??
+Hirva Mehta Can you rephrase it? Are you saying why we can't say that strings ending with 00 or 11 belong to xww^r ? Because only a subset of strings accepted by xww^r ends with 00 or 11 i.e. when length of w is 1.
If length of w is more than 1, say w=01 and x=110 then 110 01 10 is the string, which belongs to xww^r but does not end with 00 or 11.
NOW, if you have this confusion, why did the trick then work for wxw^r??????????
That's simple! Strings ending which are of the form wxw^r, definitely also have same first and last symbol.
case 1: when w itself is of length 1, trivially true.
eg: 1 0010 1 (w=1, x=0010) belongs to wxw^r
case 2: when w is actually greater than 1, w's first symbol and w^r last symbol have to be the same.
exhausting all possibilities.
I wish I got you as an instructor! You are soooo much better than my current instructor! Thank you for the help!
Hi sir,
in an example a^ib^4j | i,j>=1 is regular . But not in time 22:07 ... Do you please advise how this A.P concept not applicable in first case.
Waiting fast reply
Thank you very much for all these videos..i didnt even learn or understand of one-fourth of what u teach in my whole 4 months of semester..Thank you so much
in case of XWW^r,regular expression might be (0+1)*(0+1)(0+1)....so,can we say its regular.i m not sure that's y i m asking..
I also have the same confusion. If you got this can you please comment here.
This is regular, when, w = lemdda then it wil be like (a+b)*
w = (a,b)* instead of {a,b}+
Sir at 30:31 if do it in this way then we end up with same string at last which are not complement of each other is this still possible
@14m54s when you realize that,you forget to give tick mark :D
Such a clear explanation! Thank you!
Please include the topic name precisely in the title from next lectures
copied from
math.stackexchange.com/questions/282216/determine-if-a-language-is-regular-from-the-first-sight
Step 1: Look at the exponents of the different alphabets.
Step 2: Is there any relation between the different exponents?
Step 3a: If there is NO relation between the exponents then the language is Regular and Context free. eg: L= a^n b^m a^n b^m , m,n >=0
Step 3b: If there are relations between the exponents, for instance, L=a^m b^n L=a^m b^n, and the relation can be m>n or m!=n or m< n. You will need one counter here to keep a count, inrementing it by 1 for n times for a and compare with b by decrementing by 1 for n-times and you get a 0 for a match(assuming, m=n). These languages are Not Regular but context free and accepted by a PDA.
Step 4: If you have more than one relation or need more than one counter, for instance, L=a^m b^n c^k L=a^m b^n c^k, m=n=k. Here, you need 2 such counters. First, count all a's and copy this count value to another counter. Then, compare with b by decrementing it n-times to get a 0. Again, decrementing the other counter n-times to compare it with c and accept the language if both the counters are 0. These languages are neither Regular nor Context Free but they are Context Sensitive and thus Recursive, although, all Recursive languages are not Context Sensitive
so what, he explained it in better way
@30:21 as it is positive closure there should be '+' in place of '*' in RE as w,x cannot be null(epsilon)
or in the same 34:44
@@nammkyarakhah5596 what's the difference between (0,1)* and (0,1)+ ??
I was watch video no. 60 and suddenly all the videos are private. Why???????
sir regular and non regular language ki string create kr k question solve kr dan
Hi, there is a repetition of same concept @15:00 to @18:00 is also repeated from @18:10 to @21.10.
I think the real question is...what is REGULAR?
100 views alone from KP 9C KIIT. Thanks Guru
Shubham here kya haal chaal bhai.
@@nrlw-77777 senior ho kya?
Please make tha solution of (a+b)*=a(ba*)*
Show L= a^2n/n
thanks, its usful video , i just have a question? can i send u the question in private if it is okay
The regular expression at 30:32 is wrong. Your regular expression accepts even 00 and 11 which is not in the language (as x cannot be of length 0).
So the regular expression shd be as follows
1(0+1)(0+1)*1 + 0(0+1)(0+1)*0
or
1(0+1)^+1 + 0(0+1)^+0
Even in 34:44 same problem occurs.. u cannot accept 00 or 11. So in your regular expression, u need to replace * with + to make it correct.
Here at 11:40,
if L={ww| w=ab^n and n>=0}
Then L is regular.
But L={ww | w∈ (a,b)*} is not regular. as w could be anything in (a,b)*.
34:46 Can we not write (0+1)*(00+11)(0+1)* instead of what sir has written ?
If someone understands this, kindly solve my doubt.
Is language L = {x ∈{0,1} | x is the binary representation of 3*2 to the power of "n" for some
n>0} a regular language? If it is, show the corresponding regular expression.
If not, prove it (e.g., using the pumping lemma).please explain this
Thank you man ! you are the most trusted one on youtube
I appreciate that!
Bhai tu lucky hai jo iss channel p reply mil gya
wxw^r | w, x E (0, 1)^+ that means |W| and |x| at least 1 so solution would be => 1 (0+1)^+ 1 + 0 (0 + 1)^+ 0. Am i right?
Sir at 18.06 sec, how a will come?? Because n is greater than 1. There is no possibility of a^2(0)
why can't xww^r be regular? if we expand x till last digit and we can write it as (0+1)*1 + (0+1)*0 i.e ending with 0 or 1.
In 38:59 isnt by this logic every string in any language comes under regular language by (0+1)*0 +(0+1)*1 as every string is bound to end in either. 0 or 1
Sir at last, can we also add (0+1)*01 + (0+1)*10, becoz of OR operator it is choice (not necessarily) ?
@17.56 for a^2^n for n>=1 .should it be n>=0..
how can u get for n=1 a^2^1=a?????
Ravi...a correction..a few times you said a word can be of infinite length..that's not correct..Kleene closure is a set of all possible finite length words..and there are infinite number of such words..thats true.....but no word itself is of infinite length...the only way to generate infinite word is thru infinite concatenation thru infinite cartesian product of alphabet set...we do not do infinite cartesian product in Kleenex closure...
sir how wxw where both w,x belongs to a,b+ is regular
This man is just awesome...👍
at 31:20 How does 1.(0+1)*.1+0.(0+1)*.0 ensure that wR will be reverse of w as comparison is made between first and last alphabet only
Because for ALL W and WR (W can be of any length)
The first digit of W and the last digit of WR WILL ALWAYS be the same digit. All other alphabets in between can be considered as x. So we are accepting all valid strings.
but it accepts invalid strings also.............110 111 001
It is not invalid, the difference is just that in the string you've written "110111001",
the value of w is 1
the value of x is 1011100
the value of w (reversed) is also 1.
It doesn't matter what values of w and x were thought of by you in the first place!
@@abhilashpatil3862 The question is not about accepting a string..it is about testing a language
sr your automata lect. not download .i suffering some problem for online lect. plz solve this prob.
thanks for the great explanations but could you give an example with pumping lemma thanks
Excellent session. I was looking for these kind of examples
L= {a^n. b^m a^k: a+m+k>5}
can u help me? for wxw^r is regular since x can be expanded but in xww^r there is no guarantee.how? there can also be the cases where logic fails.
sir in case of XWWr if we take x as 100 , w as 100 then wr would be 001 so final string could be 100100001 in which the ending of w and starting of wr can be grouped which can make the string regular becoz in all cases either it would be 00 or 11 no other possible combination as was happening in X W Wr Y but why didn't u did that
and same with W Wr Y case
you are the best teacher of my career sir!
27.33 the very important questions nd very difficult to..
I have a doubt like many others. In the example at 31:00, it is true that X can take up strings from left and right but how do you ensure that strings that it has acquired apart from its original length are reverse of each other?
The question has been generalised way too much, by this logic every language is a regular language as all string will end with eiher 0 or 1, so (0+1)*1+(0+1)*0 will be valid for al language, what non sense
Lang. XWW^R,while expanding X if we get 01or 10 as WW^R then also will it not be ok??
34.06..
XWW^rY ..after extending x & y..stil we have to compare end of x and start of y..isn''t it?
At 10:40 the language ww^r is not just palindrome but an even palindrome. So the string "aba" is not part of the language.
L = {w c w^R d} where w,c,d ∈ {a, b}∗
Is it regular?
oh it is a great video! Thank you
mashallah very very good teacher !!
thank you
Nice, but why didnt you teach pumping lemma...its there in our syllabus :(
very informative. Thanks sir..
dude u rock... tame those high tuition fee institutions...
sir, i am looking for context-free grammar and pushdown automata
thank you sir for your help on my previous topics
Sir, if a language L is defined over {a,b}* and which no of a's is a perfect cube. Is this a regular or not??
@Gate Lectures by Ravindrababu Ravula , sir there is mistake at 17:50. (a)^2^n | n>=1 , L={a^2,a^4,a^8,a^16........} it is in G.P. You wrote L={a,a^2,a^4.....},{a} should not be there.
Removing {a}, It's still not in AP since there's no certain pattern for L={a^2,a^4,a^8,a^16........} for a finite automata.
What r various models to represent regular language
And what about this Language?
L={wx^n | w is an arbitrary string containing x and y of length n} E={x,y} IS THIS LANGUAGE REGULAR OR NOT?
CAN SOMEONE WRITE ME ALL EXAMPLE, THANK YOU!!
regular w is finite and rest is in ap
L={anbn|n>=0} is this Context Free Language
a raise to n and b raise to n
+Teja Kundaikar yeah ......... It's a context free language.
if L1and L2 are non-regular languages then prove or disprove that L1 u L2 (union) is also non-regular. Can you prove this please?
Consider L1 a^mb^n m=n and L2 as a^mb^n m not equal to n. Both are not regular languages(They areContext free languages ) but their union is L3 a*b* which is regular. Hence disproved.
what is the use of finding the string is regular or not?
Cameraman knows when to cut.
Its edited
@@priyakparmesh check mark by sir is the indication for the cameraman.
@36:30 Sir I was having some doubt regarding the problem. Now I found sir saying that the language is not regular ,why because even if we cause 'x' to extend to consume all but the last two symbols in ww^r then we are not guaranteed that the string shall end in '00' or '11'. Now we need some specific criteria to accept an input string. I find in many of the comments people saying what if we change the FA to accept such that the last two strings are 00,01,10,11, Then what is the use of the question? It shall be accepting each and every strings and I hope we do not want such thing to happen. Now moving on into the details, In the questions xww^ry sir said us a way in which we could make a FA out of it. As per the explanation it shall be accepting iff it has 00 or 11 anywhere in the input string irrespective of the what x, w or y we give to it. Now there is no correspondence with the output we get in this case from the machine w.r.t. the output we expect. Suppose in this xww^ry we assume x=011 and w=010 and y = 00 give an input as 011 010 000 00 , since we did not give w^r the actual value, we should expect a non acceptance but the FA actually accepts on seeing the 11 of 011 in the X. what we are sure is that if xww^ry is given in the actual correct form such as 011 010 010 00 we shall get an acceptance which is as per our wish. (This is not guaranteed in the previous case if we assume in the faulty FA design that the string w is either 0 or 1 [which is the case if string is assumed to be of the form X00 or X11 ], in such a case even if we give a correct string 011 010 010 as per the x and w I have chosen we shall get not accepted while it should have been accepted as per the language.) The sloppiness which we are able to introduce is due to fact that the length of x and y is not clearly mentioned in the machine definition and we can work out at our ease. (If you feel that a non deterministic turing machine, which is the most powerful machine, (which is a loose upper bound on the language type but more specifically a non-deterministic pushdown automata shall be more apt here) can accept the string as per the exact requirement, the NTM can wait for any length of X [branch accordingly] and then even guess to have seen w and then accordingly check w^r and at last consume y in one of the various branches possible. But here what shall happen is that it shall assume any x [not that what we give] upto the point of seeing a 11 or 00 then assume the first 1 of 11[or 0 of 00] and assume it to be w and the last 1 of 11 as w^r and give the answer as accepted provided we have atleast a non null y . This is similar to what sir designed. ) Now in the @36:30 problem if we give the input of the form of xww^r to a NTM then we can cause it to read the input from the right hand side, (read the tape to the last symbol and then move head from RHS to the LHS) then we can guessed to have seen w^r then check for w non deterministically and if w is seen then check for a non null X. since there is no such sloppiness here, definitely the language in @36:30 can be accepted strictly and this why I feel it is not regular. And I feel sir also explained the same... [Note than in the NTM solution if the entire string xww^r ends in 00 or 11 then the machine shall guess w^r=0 (or 1) and accept accordingly provided there is non nulll X.] Sir could I grasp the concept? [for simplicity to explain the concept myself I stated NTM but NPDA shall be more appropriate and note that language accepted by NPDA is also accepted by NTM]
th-cam.com/video/WkTm4joAlco/w-d-xo.html
This video will resolve your doubt.
TLDR;
The input is always a string, even if you designate 'w' yourself, the machine will always look for the pattern wXw^r, it doesn't matter what you assign yourself, logically it will be always correct. eg let's say we have input string 'ababaa' even if you designate w = 'aba' => w^r = aba , bt logically it doesn't matter what you think, for the machine can interpret in the form wXw^r where it will make the length of w and w^r == one
I can't get the point that how a^n*b^n is not regular whereas a^n*b^m is regular????
Please explain 🙏
bro even i didn't understand it . did you find the reason?
@@tavneetsinghkhurana8432 yup bro, I got the answer...
a^nb^n is not regular because u cant construct a finite automata which may accept this language....
But a finite automata may be constructed for the a^nb^m.
No fininte automata can reject cases where n!=m.
00:21 One thing you SHOULDN'T understand is.. :D
sir is this is full course becuse the wesite link is not working
didn't understand the problem in 12:10 ... how is it regular??? *length is not bounded???
Even strings with infinite length (not bounded) can be regular, in that case we have to see, if while evaluating the string, the requirement of memory is finite or infinite.
here when we take a^nb^mc^k, so while constructing the outcome, "a,b,c" all three of them are independent of each other as they have different powers (n,m,k), had it been an example like (a^nb^nc^n), then once we have evaluated 'n' number of a's,next we have to make sure that no. of b's should also be 'n' and equal to 'a', therefore in the first case (a^nb^mc^k) the string will be regular and in second case (a^nb^nc^n) string will be irregular.
At 31:00 w=011 wr=110 , then 011001000 this satisfy the RE but is wrong bc it should be 011.001.110
hey..38:55...for the case u said XWW(r) cannot be regular.....for all cases...as it might not end with 00 or 11 every time..but if the question is changed to strings that end with only 1 or 0...then the design can be for a regular language right????
Not only that cant the string definitely end with either 00 01 10 or 11
Sir can u pls explain problems on pumping lemma??
Sir in this vedio at 22.38 min u have explained that a pow(i) b pow(2)pow(n) is not regular as because of b's pattern but sir I think pattern is there like when n is 1 it is b*b when n is 2 it is bbbb when n is 3 it is bbbbbb and so on it is in A. P. Plz correct me. Sir if I am grasping it wrongly
actually, the pattern is bb, bbbb, bbbbbbbb(8 b's not 6).. which is not an ap.
no of a's in w ( mod 3 )
Ajay Sharma it is regular because it would yield finite no. of strings as mod 3 gives 0,1, 2 as remainder
strings are null, b,bb, ab (other combination ba), abb (other combinations bab, bba), aabb (other combinations baab, baba, bbaa, abab, abba)
so in RE you can combine them with + (i.e union of all).
THanks a lot sir
sir your video r esy to undrstnd . bt wht about tunning machine
CFBR
Would you explain my hill theorem language please
He looks great
How to give more than 1 like on a youtube video ?
Thanks alot
Hi
RAVI
thank u so much sir for u valuable work..my all dobouts now clear
.. sir please make a video on examples of CFL..
Can't understand his accent very well...