Operations on Regular Languages

TOC: Operations on Regular Languages in Theory of Computation.
Topics Discussed:
1. Union operation on regular languages.
2. Concatenation operation on regular languages.
3. Star operation on regular languages.
4. Theorems on Union and Concatenation.
Full Course on TOC: goo.gl/f4CmJw
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Follow me on Instagram: @jaiz_itech (bit.ly/2M3xyOa)
Contribute: www.nesoacademy...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacademy...
Website ► www.nesoacademy...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#TheoryOfComputation #TOCByNeso #RegularLanguages #AutomataTheory

[@starzone9843]

Sir, i am binge watching your videos.. i have already watched 14 of them, your way of explanation beats our professors. Keep it up 👍🏻👍🏻👍🏻👍🏻 big fan👍🏻

[@marxman1010]

Better than other automata online courses, surprisingly articulate.

[@praviveekray1907]

​@Radar123 to 🔥

[@kartikforwork]

but this is 9th feku

[@prashantpaliwal2286]

Thanks man, along with automata i am also improving my grammar or vocab from comment section. Today I learned the word -
binge-watching.

[@captainstark5496]

This teacher's professor is my professor

[@Furious_footballs]

Surely I will donate some money that I could afford when I get my first month salary........Hats off for your sincere hard work and this is my first comment on UA-cam.

[@shariquatkhan]

I wish you were my college automata teacher😍 Taught so well. Thank you☺

[@NeoAshishWecan]

Of course

[@rajanalasaidheeraj4887]

He works in my college 😍😍😍😍😍😍😍😍😍🥰🥰🥰😘😍🥰😍

[@ThePhlox99]

Theorem: The class of regular languages is closed under union and intersection. That
is, if L1 and L2 are regular languages, the so are L1 ∪ L2 and L1 ∩ L2.
Proof Lets start with the union. For simplicity, let us assume that L1 and L2
are languages over the same alphabet Σ.
Since L1 is regular, there exists a DFA
M1 = (Q1, Σ, δ1, q1, F1) which recognizes L1.
Similarly, there exists a DFA M2 =
(Q2, Σ, δ2, q2, F2) which recognizes L2.
To prove that L1∪L2 is regular, we will construct a DFA M∪ which recognizes L1∪L2 =
{w|w ∈ L1 or w ∈ L2}.
The idea: M∪ = (Q, Σ, δ, q0, F) simulates a parallel execution of M1 and M2. M∪ is
defined as follows:
- Q = Q1 × Q2;
- Σ is the same;
- δ((q1, q2), a) = (δ(q1, a), δ(q2, a));
- q0 = (q1, q2);
- F = {(r1, r2) | r1 ∈ F1 or r2 ∈ F2}
To prove correctness we need to show that w ∈ L1 ∪ L2 if and only if M∪ accepts w.
This, in turn, follows from the fact that (r0, r1, . . . , rn) is a computation of M1 on w, and
(t0, t1, . . . , tn) is a computation of M2 on w, if and only if ((r0, t0),(r1, t1), . . . ,(rn, tn))
is a computation of M∪ on w.

[@deepakchand6360]

Grt respects 🙌 bro

[@nitinkymar9468]

@@deepakchand6360 Respect and good wishes

[@sathyasubrahmanyam4166]

Thank u brother

[@yt_souvik]

I finished this lecture just now. Please upload those two theorem proofs in Another video, it will be helpful for us.

[@MSneberger]

For proof that Regular Languages are closed under Union Operation see Theorem 1.25 on page 45 of Sipser's textbook. For proof that Regular Languages are closed under Concatenation Operation see Theorem 1.26 of Sipser's textbook on page 47.

[@alan2211]

Sipser no make sense.

[@diptamanguha155]

Sir..your videos are great.These helped me a lot.Will it be possible for you to upload videos on C programming,data structures and algorithm?

[@kasozivincent107]

Hello. I think u messed up the Kleene star operation. It is not just a concatenation of all elements of A. It contains strings of 0 lengths, 1, 2, and so on. So I guess they should even be separated by commas. I suggest it would be better to use union notation. A mathematical definition would suffix for this, if L = {a,b}, L* = {@, a, b, aa, ab, ba, bb, aaa, ...} not just a concatenation of symbols from the alphabet that L is defined. {bbabababbabaabababa} for example is just an element of L*

[@gedelasivakrishna]

Thankyou !!

[@flovous]

Thank you for the content, as always. Very easy to follow and understand

[@adiyc2909]

Thank you ,sir . Very easily understandable . But can you please provide the proofs of the theorems also ?

[@ktwsahil7445]

Thank you so much sir

[@ktwsahil7445]

Welcome beta

[@venkatasatyatejakapuganty]

please upload a video on proofs of the theorms at last

[@jaiashutosh2181]

for union purpose dont you think we should mention and like x belongs to a and x belongs to b. please correct me if i am wrong.

[@AnonymousDeveloper1]

Hello, question not specific to current subject but I must ask you:
Will you record data structures and algorithms tutorial series in the future?

[@AnonymousDeveloper1]

Wow, nice! I would like to see this series because you are great.

[@shivamdubey7599]

Please bring up the algorithm part as quick as you can. It would be very kind of you.

[@Aba9846]

Awesome! Where can we find these videos?

[@fnaticbwipo1222]

for proof of the following theorems I will use the fact that regular languages are those that can be described by regular expression, let's say we have 2 regular languages A and B, and their regex be p and q, then concatenation of those languages can be described by pq (first part will describe string from A and second part string from B), as for union we can use | operator for regular expressions and describe language by (p | q) since union contains strings that are present in both languages.

[@alitcher4425]

Id like proofs of those 2 theorems please. Thank you for this video as well sir!!!

[@fcreany9147]

Should the AUB and A•B included the Epsilon ?
Such that
AUB ={ε,pq ,r,t,uv}
A•B={pqt,pquv,rt,ruv, ε,pq(=pqε) ,r,u,t}

[@NSHAIKAMEENA]

No

[@hygieia5672]

For anyone wondering about this in the future, and to be more helpful than just "No", only A* can contain epsilon because in the definition it says there are k elements of A where k can be any positive number including zero. k being zero is how you get epsilon aka no elements at all.

[@roshannalawade7389]

sir give me the proof of this

[@tharunkumar8430]

Your videos pretty great SIR ..😃
Guy's do follow this channel is very useful to gain knowledge easily...
👍👍

[@Kshirabdi.Tanaya]

Sir please make a video on theorems.🙏🏻

[@mercyoroc8721]

Thank you so much to explaining us 😍😍

[@notsphinxz]

Thank you Neso Academy I watched some of FSM videos are very Interesting and Entertain to Learn for my Computer Science Career! Cheers UP

[@ankitjain2398]

Sir please record videos on Computer Networks of CS branch

[@dillipkumarsahoo5017]

Sir please make a video of proving the
all theorems of regular languages

[@technicalinfochannel66]

dear sir kindly explain the theorem of class of regular language is closed under the "kalena" star operation

[@aydict]

kleene*

[@shivrajkhose7875]

please upload videos of turing machine,recursive and recursively enumerable language

[@omkarmarbhal]

Best Tuts Ever........!!!!

[@pushplataraina51]

hi sir,
i want
proof of theorems

[@rohitpandey4]

Sure sir can you make a video for Proof of Theorem1 and Theorem2

[@jsbbatth8667]

Please make a video on proof of the theorems

[@jeetdas4799]

Helps me alot....tnk u sir ji

[@sasswithdivyanshi]

This is so well explained ❤️❤️❤️❤️❤️❤️❤️

[@KNIGHT-yy7nh]

hii

[@KNIGHT-yy7nh]

@divyanshi hello

[@KNIGHT-yy7nh]

hi

[@kartikforwork]

@@KNIGHT-yy7nh are bhai itna bhi ky karna, tum jaise log nam dubate ho

[@lakshaybansal2470]

@@KNIGHT-yy7nh bhai firse try karke dekh 1 saal aur hogya

[@Ana-el3gk]

Amazing! thank you

[@trywellwashington7506]

concatenation: cartesian prod, order of elements in pair immaterial

[@akshunkc6884]

hi sir nice TOC series...plz also upload profs of these theorems...?
thanks in advance...

[@devmahad]

Union, Concatenation & star.

[@saidurgaprasad5172]

Thanks you sir

[@anirudhyasarkhel8247]

Sir please provide proof for those 2 theorems, imp for exam

[@sourjadhar9332]

The star one is also called kleen closure .

[@sathirajumadhavarapu3065]

sir, could you please explain proof of two theorems

[@satwikyalamarthi1162]

We want proof...... Can you please explain

[@adhishagammanpila]

Really appreciate if you could do the proof too

[@Montserratx]

Can you explain to me this example, please?
A*={a*,b*,a*,b*}

[@chandanpatra3850]

sir can I use this answer for closure properties of regular sets.

[@uditisinha357]

what is the significance of putting k => 0 for A*?

[@apporvaarya]

nice concept

[@dhanushsivajaya1356]

Thankyou sir

[@richierabbit2733]

please please make vedios on data structures

[@muhammadashfaq8032]

Love from muzaffer garh Pakistan

[@Ankit-we8ym]

dear sir are you also teaching any other subjects for cse students

[@nitishbharat9942]

Yes 👍

[@risingsingh3424]

How to visualise practically the concept of regular languages

[@AhamedKabeer-wn1jb]

THANK YOU..

[@saptarshiroy3943]

Sir, can you provide the proof of Regular language expression?

[@kishankanabar6620]

sir i can find one ambiguity over here.When you are declaring definition of star,i.e. A*={x1x2x3...xk:k>=0 and all xi belongs to A}.So when k=0,what would be the concatenating string?and if you are saying it is a null string then again ambiguity arise because as you said all xi,including x0 should belong to A,but that is not in the actual case.Please make it clear.

[@vivekkumar-xc8vq]

Kishan Kanabar Hey... Are you not aware of the fact that all sets have a null element i.e. null element belongs to each and every set....

[@ronikseth6742]

sir i want regular language's many types of problem with solution for better understand.thank you.

[@knvssandeepbolisetti5008]

Sir pls give the proof for theorems

[@ashisraha9263]

Sir I need proves of two theorem of regular languages. If you send me then I will be thankful to you.

[@imhsk1037]

pls clarify our doubts

[@RNCSSakshamBhatia]

If possible please give the proof of theorems.

[@moazzamali5995]

Sir plz..show some prove. Of this theorem

[@-kurdush]

plz.. explain proofs of those theorems

[@akshaykhachi8565]

If L={ab, c}...what will be L^3....??

[@ishmitabasu9623]

Can i please get a proof of the two theoram?

[@teenanandwani8823]

Sir please explain Kleen's theorem...

[@saraswatibepari8233]

Sir , give us the prove of this 2 theorem ... please

[@Uttamkeshri726]

In A* prq also be there

[@durgarajeswaritalluri4124]

sir will pqpqr is also in A* ??

[@mantashawasi1991]

Yes

[@fizzsfizz7617]

Video was awesome but You should provide proof to complete topic

[@dulldelusion]

Sir predicted "RRR" Film before it was a thing...

[@nebiyumesfin9620]

Set of regular languages over a given alphabet is not closed under
a) union b) complementation
c) intersection d) none of the above

[@thirumenipharma2612]

what about (A+B)*

[@VikashSingh-sq2yy]

Sir please give the proof of the theorem.

[@barathkumarsr9890]

Please prove the theorem 1& 2 sir

[@sambhavjain9382]

can we have the proofs please?

[@pedarayududola1672]

what is regular language

[@CyrusXIII]

Thank you :)

[@shankarreddy4674]

What is it mean every one commenting like this

[@laxmiwodeyar3113]

Sir please do proo

[@UniversalUnicorn]

5:35/5:57 : 🦭🦭

[@continnum_radhe-radhe]

❤❤❤

[@pranaysahariah6193]

Proof of the therom sir pls

[@msm8416]

Proof for Theorem 1,Theorem 2 plz

[@shaganpreetkaur1397]

thermos of regular languages expain sir

[@smartyabhi9678]

Explain hota hai 😜

[@vlogsnepal9550]

sir proof please on union operation

[@shinigamiryuk4183]

my teacher plays your videos in lectures

[@naveenraju3540]

sir proofs please

[@bhishmapitamah3681]

5:52 your device is fine

[@SanjeevKumar-td4bj]

sir please upload proof of this video

[@neiljohn2637]

Level 9 reached @!

[@vishalsaxena4869]

need proof

[@saideep9808]

sir we want proof

[@khushiahuja82]

sir bta do proof!!!!

[@swadheenta.957VBTS]

💜💜

[@15tefera]

Sir, I want bob please

[@sanathramesh7254]

Proof please

[@sudiptacoachingcentre4118]

Want the proof

[@addagallanaresh4044]

Want proof

[@DnyaneshwarPanchaldsp]

💐💐💐💐👌

[@USBEN.]

Theorm : Stating the obvious facts with fancy english .

[@manavkalra5279]

And fancy maths.

[@dqfans3364]

prooof