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.
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.
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.
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*
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.
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.
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.
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👍🏻
Better than other automata online courses, surprisingly articulate.
@Radar123 to 🔥
but this is 9th feku
Thanks man, along with automata i am also improving my grammar or vocab from comment section. Today I learned the word -
binge-watching.
This teacher's professor is my professor
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.
I wish you were my college automata teacher😍 Taught so well. Thank you☺
Of course
He works in my college 😍😍😍😍😍😍😍😍😍🥰🥰🥰😘😍🥰😍
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.
Grt respects 🙌 bro
@@deepakchand6360 Respect and good wishes
Thank u brother
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.
Sipser no make sense.
I finished this lecture just now. Please upload those two theorem proofs in Another video, it will be helpful for us.
Best Tuts Ever........!!!!
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*
Thank you for the content, as always. Very easy to follow and understand
please upload a video on proofs of the theorms at last
Hello, question not specific to current subject but I must ask you:
Will you record data structures and algorithms tutorial series in the future?
Wow, nice! I would like to see this series because you are great.
Please bring up the algorithm part as quick as you can. It would be very kind of you.
Awesome! Where can we find these videos?
Your videos pretty great SIR ..😃
Guy's do follow this channel is very useful to gain knowledge easily...
👍👍
sir give me the proof of this
Thank you Neso Academy I watched some of FSM videos are very Interesting and Entertain to Learn for my Computer Science Career! Cheers UP
Thank you so much to explaining us 😍😍
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?
Thankyou !!
This is so well explained ❤️❤️❤️❤️❤️❤️❤️
hii
@divyanshi hello
hi
@@KNIGHT-yy7nh are bhai itna bhi ky karna, tum jaise log nam dubate ho
@@KNIGHT-yy7nh bhai firse try karke dekh 1 saal aur hogya
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.
thanks bro
Id like proofs of those 2 theorems please. Thank you for this video as well sir!!!
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}
No
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.
Thank you ,sir . Very easily understandable . But can you please provide the proofs of the theorems also ?
Amazing! thank you
Helps me alot....tnk u sir ji
Thank you so much sir
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.
Sir please make a video on theorems.🙏🏻
dear sir kindly explain the theorem of class of regular language is closed under the "kalena" star operation
kleene*
Sir please make a video of proving the
all theorems of regular languages
hi sir,
i want
proof of theorems
Thanks you sir
Sir predicted "RRR" Film before it was a thing...
please upload videos of turing machine,recursive and recursively enumerable language
Please make a video on proof of the theorems
Sure sir can you make a video for Proof of Theorem1 and Theorem2
Love from muzaffer garh Pakistan
concatenation: cartesian prod, order of elements in pair immaterial
Sir please record videos on Computer Networks of CS branch
Union, Concatenation & star.
The star one is also called kleen closure .
nice concept
We want proof...... Can you please explain
Thankyou sir
Really appreciate if you could do the proof too
THANK YOU..
hi sir nice TOC series...plz also upload profs of these theorems...?
thanks in advance...
Sir please provide proof for those 2 theorems, imp for exam
sir, could you please explain proof of two theorems
sir can I use this answer for closure properties of regular sets.
my teacher plays your videos in lectures
what is the significance of putting k => 0 for A*?
Level 9 reached @!
please please make vedios on data structures
dear sir are you also teaching any other subjects for cse students
Yes 👍
Sir pls give the proof for theorems
In A* prq also be there
Can you explain to me this example, please?
A*={a*,b*,a*,b*}
pls clarify our doubts
Sir please explain Kleen's theorem...
How to visualise practically the concept of regular languages
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.
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....
Sir plz..show some prove. Of this theorem
5:35/5:57 : 🦭🦭
If possible please give the proof of theorems.
Sir, can you provide the proof of Regular language expression?
sir will pqpqr is also in A* ??
Yes
Video was awesome but You should provide proof to complete topic
Thank you :)
What is it mean every one commenting like this
sir i want regular language's many types of problem with solution for better understand.thank you.
sir explaine the proof about two theorems
If L={ab, c}...what will be L^3....??
Can i please get a proof of the two theoram?
Sir , give us the prove of this 2 theorem ... please
Set of regular languages over a given alphabet is not closed under
a) union b) complementation
c) intersection d) none of the above
5:52 your device is fine
what about (A+B)*
Sir I need proves of two theorem of regular languages. If you send me then I will be thankful to you.
Sir please give the proof of the theorem.
can we have the proofs please?
Please prove the theorem 1& 2 sir
❤❤❤
what is regular language
Sir please do proo
thermos of regular languages expain sir
Explain hota hai 😜
Proof of the therom sir pls
Proof for Theorem 1,Theorem 2 plz
sir proofs please
sir proof please on union operation
sir please upload proof of this video
need proof
Proof please
Sir, I want bob please
sir we want proof
sir bta do proof!!!!
💜💜
Want the proof
Theorm : Stating the obvious facts with fancy english .
And fancy maths.
💐💐💐💐👌
Want proof
prooof