Regular Languages

[@bayyareddy8614]

Thanks

[@shavkat95]

the first example can be modelled in a FSM. First u make a tree structured DFM with 'a' for left and 'b' for right. then wherever u end up at the fifth character, u continue accordingly.

[@AabhusanAryalOfficial]

Exactly!

[@np1525]

U could also make an NFA ith an epsilon transition back to the start after reading ababb

[@leonh2140]

Yeah I also found that :( It really confused me

[@acturk_]

i think this is true only if the alphabet is equal to {a,b}. if the alphabet includes more symbols your solution would be wrong

[@Amy-mo9ki]

yes

[@BossLikesShenanigans]

Why is the first example not a regular language? If the language just consists of one string then can't you just have all the states of the machine be Q ={a, ab, abb...} and then the transition function for each state would be whether the next symbol is seen, and if it isn't, we send the machine to a dead state? EDIT: I just saw your reply to a different comment. I didn't understand the example. For those wondering the example was about whether it can detect if a string repeated itself.

[@zerobit778]

To be clear. Let S to be a string. We could have DFA to recognize S* just simply by loop to the beginning after a full match. What Neso mean is just that we could not have a DFA to find a arbitrary S's repetition. To recognize a specific string's repetition is a different story with arbitrary string's repetition!!!

[@whiteheadiceprince1506]

if ababb needs to be repeated exactly n times then we increase the number of states (copy the FM n times) wouldn't that work? ((A))-a->((B))-b->((C))-a->((D))-b->((E))-b->(((F))) - - a - -> ((B)) - - NFA for any non-integer repetition. (A)-a->(B)-b->(C)-a->(D)-b->(E)-b->(F)- - a - ->(B2)-b->(C2)-a->(D2)-b->(E2)-b->((F2)) NFA for exactly 2 repetitions.

[@zerobit778]

​@@whiteheadiceprince1506 This string you mean "ababa" is a specific one. You can have DFA for this specific string for any repetition of times. But the DFA you constructed for "ababa" may not work for other string like "abcabc". What Neso mean is you can not have DFA works for all types of string with repetitions.

[@whiteheadiceprince1506]

@@zerobit778 ohh ok thank you

[@StudyArtist-pl2bn]

00:06 Regular languages are recognized by finite state machines. 00:53 Regular languages are recognized by finite state machines 01:44 Finite State Machines have limited memory 02:30 Regular languages follow specific repetition rules. 03:25 Finite state machines have limited memory, making string repetition impossible 04:12 Regular languages require the number of 'B's to match the number of 'A's. 05:05 Counting and storing in regular languages 05:49 Regular languages require less memory and can be recognized using finite state machines.

[@Bananainacar]

Wonderful video! Everything is explained in such a clear and efficient way. You're the best.

[@nguyentuananhphan8644]

Thank you sir for your clear explanation, this series really saves me!!! God bless you!

[@hectorg362]

I freaken love you and this channel for this content!

[@pailguy7157]

The first Eg. (ababbababb) repeats only 2 times, so without saving it we can simply construct a DFA that gets all inputs as a sequence of alphabets. In this case isn't it regular language?

[@ohaRega]

Pail guy and Calvin, you're both correct

[@tapajkumardas9973]

If the repeating part of the string is of finite length, I think we can construct DFA for it. I think what he meant to say is that, we can't construct a DFA that accepts all strings that are arbitrary repetition of a smaller string.

[@rohandesai4585]

But can't we construct a DFA for any number of ababb substring to occur?

[@georgiosargyris3073]

For the first example (ababb)* is a regular expression that generates the string of the first example. Since there is a regular expression, there is also a finite machine. Instead, my language accepts even when ababb is repeated n times (n greater or equal to 0). Maybe, the guy on video implies what Tapaj says.

[@Rohith_E]

The rule for language 1 is: 'The first n Symbols repeat once'. These n symbols can be anything. Just as an example he mentioned ababb.

[@cindychaba]

Amazing content.Keep up the good work.

[@vipinsclasses9354]

i like your lectures , brother. you got one more subscriber.

[@KiimzB]

This was such a good video. Very clear. Thank you

[@Oneminutecover-dx8re]

Don't get how FSM can't store strings when in the previous lectures of DSM we transfer all string to next state(or that's how I understood it )

[@ijazkhans5521]

The expression ( ababbababb ) that you discussed earlier in this lecture is regular expression and you say: it's not a regular

[@deadoralivecowboy1401]

Please make a video of the proof of the first theorem you wrote !! I have an exam in two days , I know it is too late for me but for other generations maybe not so late :)

[@nameless2850]

Lol too late... Have exam tomarrow

[@deadoralivecowboy1401]

@@nameless2850 every cs video's fate I guess... Good luck ,man !!

[@abhisheknegi2888]

@@deadoralivecowboy1401 and now my fate🥲

[@charname2077]

@@abhisheknegi2888 Now mine

[@minhnguyennhat3551]

My time has come… I have exam in 3 days 😅

[@stefanwullems]

I'm missing the explaination why finite state automata cannot count or store strings. Maybe an example where we try to build a fsm that tries process these langages but fails would have been useful.

[@Nano-ih3ig]

It doesn't store any previous input of the string that has been provided. You only move forward with the current input. For eg. if w is a string with symbol {a, b} so to recognize ww, you need to store w first, which is not possible in FSM.

[@MaxAndHisBike]

Theoretically you could build a state Machine which recognizes the second language, as long as you can build a machine with 2*n-states

[@miro-hristov]

You said that a language is regular if it can be recognized by FSM. RegEx has a lot of modifiers that allow it to count repetition or use memory. Eg. "{2}" is a quantifier - Match 2 of the preceding token. Or "\1" is Backreference - matches the result of capture group #1. Does that make Regular Expressions not a regular language? I'm a little confused...

[@korigamik]

Yes.

[@hassanhashemi6478]

i love they way you explain things.

[@Alkis05]

A video of what is regular language that shows examples only of non-regular languages. Don't you think it would be a good idea to illustrate that regular language is?

[@nirmalasanapthi7548]

Respected sir By using 6 states + 1 dead state we can construct a dfa for ababbababb

[@handleh]

Your dfa only accepts ababbababb but it should accept any ww where w is a string thats why we cant use dfa

[@kasozivincent107]

I doubt if 6 suffices, we need 10 + 1 dead state.

[@elevated_existence]

By the way is a language over {a,b} that contains aabb in itself regular or not

[@graffitiabcd]

What if you define the language in the first example as follows: L = {V, S, T, P} where, V = {a, b, S, A} T = {a, b} P = {S->Ab, A->AbAb, A->abab} Would that not make the example a regular language, unlike the second one in which a memory of N is required?

[@matamorosa]

yeah I also don't think his first example is valid

[@hakanyalcn6826]

can you explain that why ababbababb is not recognizing with FSM ? i can create ababbababb by using 10 state(one state point to dead conditions) simply.

[@gamereplayhq]

Yes, although you can make it, the question here is, suppose you want user to just input "ababb" and insert rest of the values yourself to generate the result, such action would be possible if we have some sort of memory from which we could retrieve the values and use them as input to run our machine further on its own without user intervention, however in FSM, user must give some input to move states, there is no dedicated memory bank that could provide input to machine.

[@eva42sh]

The degree of complexity and the way of performing the functions characteristic. Automatic Grade 1

[@azeemqureshi4963]

wow what a nice video you made very clear and very easy...

[@manasuniyal4250]

The first language is regular as it can be represented L={(ababb)^n : n>=1), provided lambda is not accepted, for which a DFA can be constructed.

[@sajalchhetri2476]

why is second one not a regular language in when in previous video we designed a dfa fo aabb which follows the structure aNbN n=2?

[@niburX]

I think it's because in this video, it's not only n=2, but for all natural numbers (i.e.: n≥1).

[@ashikghosh6166]

Thanks!❤❤

[@LorenzoLeonardini]

Actually ababbababb is a regular language If the language is just that you can have a simple machine which recognizes the string. If the language is "ababb" repeated n times you can still have a machine which recognizes it: just 5 states to recognize the basic string, only the last state is a final state and if you are in the final state and read an "a" you start over from the first state

[@purveshdubey7562]

I also think so, we can easily construct nfa for that

[@heroslippy6666]

It is not asking if you can check if the string "ababb" is repeating. It is asking us to check if we need to memorize an arbitrary string. Our Finite Acceptors can only remember a singular state so it would require an infinite amount of nodes to remember every possible arbitrary string.

[@sparshsondhi1424]

Respected Sir In the second example, can we not make a DFA with an infinite number (limited only by total memory available) of states in a line, each moving forward on input A and back on input B? That way we can keep our initial and final state the same and still have a way to count the number of A's and b's.

[@eeshaan1539]

it shouldn't be of the form ababab, but should be aaaa....bbbb....

[@sparshsondhi1424]

@@eeshaan1539 Agreed, but what trying to imply is making a ladder.... Ababab strings would never reach the initial/final (because they're the same) state without having an equal number of A's and b's... Imagine going up 3 steps and coming down 3 steps as an analogy

[@sparshsondhi1424]

Now that I think about it.... This is quite impractical. A DFA needs full information about all states and I can't define how the start and end states would be structured

[@arturo7392]

you forgot to put an example of a regular language... almost a perfect video

[@J4WAD]

all the 4 examples before are regular languages, yall lazy.

[@naseerrahi7597]

What r various models to represent regular language

[@shivrajkhose7875]

very helpful

[@hygieia5672]

Good but spoiled a bit by specifying five letters specifically and not N letters. With five (or some other constant) letters the language is finite and you can construct a DFA for it, it is regular. If it is some arbitrary number of letters than you cannot.

[@studentstudent1237]

Thank you Sir for explaining this ,is regular language same as regular expression?

[@rahuldwivedi9236]

No

[@user-mi8ew2to8e]

If you can design RE, you can derive RL and vice versa

[@shubhamkohli7719]

I don't understand practically about regular expression i just understand the theory.

[@fnaticbwipo1222]

more formal way to define a regular language would be that it can be described by a regular expression.

[@sudiptacoachingcentre4118]

Totally helpful

[@logiclassan7115]

set the speed to 2x

[@fupopanda]

It's good that he goes slow, allowing you to speed the video up when you need to, and leave it as it is when necessary as well.

[@Farahat1234]

Why?????????

[@devmahad]

Regular Language -> if some FSM recogonizes it. FSM -> Very low memory.

[@M-ABDULLAH-AZIZ]

Is this language {(0^n)(1^m)|(n+m)is even} regular or not?

[@raulcalvomartin2979]

Is not regular because you need to count n and m to know that the sum is even.

[@NLogSpace]

@@raulcalvomartin2979 No, it is regular! Checking whether n+m is even does not require you to remember n and m completely, it is enough to remember the remainder modulo 2, which can be done with finitely many states.

[@dhanushsivajaya1356]

Thankyou sir

[@ManpreetSingh-pn2hu]

watching all the videos one day before the exam on 2x

[@nabhavlogs371]

example 1 is a string, not language,which we can represent using DFA

[@ziliestarrive]

It's for recognizing M1M2, where M1 is a string and M1=M2, that's the rule for the language.

[@manasimukhi9124]

if Σ=(0,1) then describe Σ* 1Σ* Answer pls?

[@omkarsuralkar8099]

Thank You

[@limishavyas2496]

costruct regular grammer for language is avalible or not......?

[@_BE-A_SaurabhNehe]

Thanks alot sir

[@henriquepavani88]

And what if its a language that start with a and finish with b ?

[@vikaspanthi663]

Awesome video...

[@naavedali7303]

thank you sir

[@madhabkafle8072]

List some examples of regular language's

[@gedelasivakrishna]

thankyou !!

[@1234Christodoulos]

how do we know how to split the "aaaaaaabbbbbb" into x y z ? is it just random

[@shinigamiryuk4183]

my teacher plays your videos in lectures

[@ravikumarpal662]

speed of 1.5 is sufficient for beginners

[@bdjeosjfjdskskkdjdnfbdj]

is there a proof for repetition --> non regular? seems like a bit of a leap for me!

[@MohamedAhmed-po1ts]

haha

[@sbc498]

Pumping lemma is the proof

[@daleeps]

finally found a good video, jesus...

[@brunoomondi5902]

Praise the Lord

[@AhamedKabeer-wn1jb]

Thank you..

[@zahidqureshi8128]

sorry sir, but first example is incorrect ...if L is regular and L^2 is also regular ...refrence introduction to FLA edition 5th by peter linz Fig 2.7 page 46

[@peymanmohsenikiasari8564]

I think he meant to find strings that are in the form of XX (that X could be any string), which is impossible to be found by a finite state machine.

[@himalatalukdar5597]

Is this lecture value for gate and other competitive exams?

[@mdnaiyerhoda9853]

this lecture is very fruitful for concept on regular language. a good concept can only make one solve questions

[@smarter_by_bit9346]

But provided that language is finite,it will be regular....please mention it

[@AhamedKabeer-wn1jb]

THANKS..

[@swagatsekhar4973]

Can u provide ur class notes

[@danielnunes3598]

fix the audio, please

[@jainlokesh318]

amazing

[@iqrahkhan2138]

video bht achi h but urdu me hoti to or be achi hoti

[@cvismenu]

Awesome

[@neiljohn2637]

8 like Shaun Tait!

[@DolaLado]

I didn't understand the first example. ababbababb. I think we can design a DFA for it.

[@eeshaan1539]

The language is { ww : w is a string over Sigma} i.e. the first and second halves of the string must be same. ababbababb is one of the strings in this language, but it's not the only one.

[@apporvaarya]

didn't get much idea

[@saikishan1000]

lol I have final exam next week let's see if ness will make me pass

[@sunnynavani5314]

now i have final exam next week so can you tell that are you pass or fail? :D :P

[@tallle2]

what happened?

[@HafizMohammede]

I hav xam nxt morning and found this video only now time :12:45am

[@vaigyanick5171]

1.75x,, you are welcome

[@nitinjain1325]

kaisa machine hai jo ek count ko bhi store nahi kar sakta hai

[@naruto07959]

yeah, right. Just like you dumbass XD

[@norhaking]

lol

[@gabrielpereiramendes3463]

#Excelent!

[@yili5761]

「どうやってやるの？」、

[@yamankaithwas5016]

NOTES ?????????????????????????????????? NOTES

[@dailydoseofact]

Any KECian😂

[@vinayaksharma-ys3ip]

👍👍👍

[@soul9126]

Any vitian😅

[@shakarwshyar2980]

Thanks