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.

Music:
Axol x Alex Skrindo - You [NCS Release]

#TheoryOfComputation #TOCByNeso #RegularLanguages #AutomataTheory

[starzone]

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👍🏻

[shariquatkhan]

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

[Furious_footballs]

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

[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.

[yt_souvik]

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

[ThePhlox]

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.

[diptamanguha]

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?

[tharunkumar]

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


👍👍

[flovous]

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

[adiyc]

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

[AnonymousDeveloper]

Hello, question not specific to current subject but I must ask you:

Will you record data structures and algorithms tutorial series in the future?

[venkatasatyatejakapuganty]

please upload a video on proofs of the theorms at last

[fnaticbwipo]

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.

[kasozivincent]

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*

[alitcher]

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

[sphinxzgamingofficial]

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

[fcreany]

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}

[Kshirabdi.Tanaya]

Sir please make a video on theorems.🙏🏻

[sasswithdivyanshi]

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

[shivrajkhose]

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