Designing Regular Expressions

TOC: Designing Regular Expressions
This lecture shows how design Regular Expressions for the following Languages:
1) Language accepting strings of length exactly 2
2) Language accepting strings of length at least 2
3) Language accepting strings of length atmost 2
Contribute: www.nesoacademy...
Website ► www.nesoacademy...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Pinterest ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
• Axol x Alex Skrindo - ...

[@haythama8563]

+ means OR, * means ZERO OR MORE, so if we translate the second expression it would be : (a OR b) (a OR b) [ ZERO OR MORE OF(a OR b) ], so the smallest possible string would be if * is Zero we would have only (a OR b)^2, therefore that RE represent any string of length at least 2. Same idea applies to 1 and 3.

[@EarFarce4]

THANKS!

[@mnaresh3382]

Refer this if Q2 seems difficult to understand In my perspective think of (a+b)* as the set containing all possible combinations from {episilon, a, b, aa, bb, ab, ba, aaa.....} So when we multiply say "aa" to this set do you there is any possibility of having an element "a" in our closure set, No we can't find one because we originally had one "a" in our set now after multiplication it was converted to "aaa" and possibly the other choice would be seeing epsilon, after multiplication it was changed to "aa" and we don't really care about all other terms since we can say for sure our set starts with element "aa" there is no way of finding an element of length one. Now just replace instead of multiplying "aa" we are multiplying what we need as a starting element which is (a+b) (a+b), and we got the answer

[@AnkitVerma-ch5oi]

you are doing awesome work!

[@apporvaarya]

absolutely awesome this tutorial is

[@ProfessionalTycoons]

We can write the second answer as (a+b)(a+b)^+ - Cross sign

[@rishubhbijlani2815]

yeah thats what i thought, are you sure about this tho?

[@CriticRoshun]

I agree

[@diodesu]

yeah, we should use the cross sign imo

[@arnabghanty8448]

GOD BLESS YOU.....❤️❤️

[@riyapal8877]

sir u are the bestest teacher ever!!!!!!

[@Vardan019]

Hi riya can you give me your phone number

[@alirizvi3506]

There is an error at 06:15, Correction: f we want single a so we should conconate with ebslon, same goes with b.

[@jonaskoelker]

Just like a list of T can be defined as either nothing, or a pair of a T and a list of T, we can do strings of length at most k in this way: e + (a+b)(e + (a+b)(e + (a+b)(e + ...))). That is, each string of length at most k is either epsilon, or it's any symbol followed by the regular expression for strings of length at most k-1. This has the property that for any given string, for every '+' there is only one choice compatible with the given string.

[@Shiva_polishetty]

If we give star for second sum it means.... String starts for empty but.. But there is no null(why we can't use cross symbol)

[@ChristianBurnsShafer]

If you're talking about why there is a Kleene Star in the second example it is because he cannot exclude Epsilon from closure. That would make it so only strings greater than or equal to three would be accepted. There is a way to write this expression using the cross symbol, but that would be less simplified.

[@dimplejain7226]

awesome videos!!!!helping me a lot

[@gunjanshinde396]

In example 3, How did we get (E +a +b) (E +a +b) ? I tried to get this from above equation. And farthest I reach is E + (a+b)(E+a+b). Can anyone tell the way ahead ?

[@gunjanshinde396]

​@Abbxs Okay, means as we are having a + b equation, we can 'or' it with itself which makes no difference to the equation and hence it is valid ? Something sound, thank you👍🏻👍🏻

[@degoaty]

What if 3 is (€ + a) (€ + b) (a+b) (a+b)?

[@gunjanshinde396]

Hello @Abdullah kamal , the comment was done far before. Later I ask my few friends and I learnt that here we are taking few (but important) fundamental different then our basic, well know algebra. So one need to accept that to proceed. Hope you will find that in the above playlist. Good Luck ahead !

[@null--404]

We can just take (a+b)* which satisfies all conditions

[@arnabdaw2587]

At 6:25, (R+R=R) is used So , one extra (a+b) is added to the expression, then u will get the above answer

[@nehakumari1251]

Plz explain it

[@yashpaliwal2219]

in the condition... string of length atmost 2.. What is the approach to convert that exp €+a+b+aa+ab+ba+bb into (€+a+b)(€+a+b) ????

[@ChristianBurnsShafer]

Understand that '€a' is a concatenation of 'a' with the empty string, returning 'a'. Interpret '+' as 'or'. E.g. € + a + aa + ab + b + ba + bb = (problem statement neatly arranged) € + €a + €b + a€ + aa + ab + b€ +ba +bb = (redundant terms added to simplify explanation) €(€ + a + b) + a(€ + a + b) + b(€ + a + b) = (factoring by identity (12)) (€ + a + b)(€ + a + b). (again, factoring by identity (12), and the desired answer) Good luck!

[@sweetykarmakar4974]

@@ChristianBurnsShafer I've seen all your Comments in this series, you're so intelligent!!! 😁😁😁😁

[@sulavthapa2042]

@@ChristianBurnsShafer Thanks bro

[@anusuabiswas953]

@@ChristianBurnsShafer can u plz xplain the 2nd one : at least 2

[@shashikalaraju5769]

@@ChristianBurnsShafer Thank you .. that's actually inspiring.

[@zackcarl7861]

I don't get it why (a+b)* when it says on language :must have atleast 2 elements ,but in (a+b)* there can be a, b ,or empty

[@Omar-ic3wc]

(a+b)* means all the possible strings that you can create from the elements a and b

[@NaveenShukla-nq6oe]

(a+b)*(a+b)(a+b)(a+b)* will answer

[@tayyab.sheikh]

If you put (a+b)⁰ then it would be 1, and 1 multiplied by (a+b)(a+b) will give you the answer of the first question, similarly you can put (a+b)² and any number in the exponent, it will give you strings of at least length 2!

[@dhanushsivajaya1356]

Thankyou sir

[@hellb0y522]

wayy better than my professor

[@Argdut1106]

Nice video. But where is Part 2 sir? Guess this is supposed to be Part 1?

[@mihaichirculete7623]

kzbin.info/www/bejne/hXypo52rZa11bc0

[@sam19r]

(a+b)(a+b)+ for Q3?

[@harsh_t]

Wrong. It doesn't produce Epsilon which is a valid output

[@degoaty]

In 6:35 What if 3 is (€ + a) (€ + b) (a+b) (a+b)?

[@AhamedKabeer-wn1jb]

THank you..

[@soumisarkar4315]

Sir please help me to solve this question The string 1101 does not belong the set represented by (a) 110*(0+1) (b) 1(0+1)*101 (c) (10)*(01)*(00+11)* (d) (00+(11)*0)*

[@maheshjamdade1]

1101 does not belong to c and d

[@ChristianBurnsShafer]

(a) First one given, second one given, choose one zero, choose 1. 1101 belongs to this set. (b) First one given, choose €, second 1 given, 0 given, third 1 given. 1101 belongs to this set. (c) First one given, unwanted 0 given. 1101 does not belong to this set. (d) This set does not contain strings longer than 3. 1101 does not belong to this set.

[@sulavthapa2042]

@@ChristianBurnsShafer Can you elaborate please?

[@umairsaeed2848]

Can any one answer this please...? Construct a regular expression defining each of the following languages over the alphabet sigma={a,b}: 1). all words ends in 3 consecutive b. 2). all words heaving atleast 1 a. Thanks...

[@Amit-cg9le]

I think the ans. of your q. are 1) (a+b)* bbb 2) (a+b)* a (a+b)* But I am not sure about my answer ok.

[@kaidokun2742]

I'm not sure what restrictions are on the language definition used here... but I based off basic regular expressions and I think my answers are simpler? L1: (a | b) (a | b) L2: (a | b) (a | b)+ L3: (a | b)* (a | b)* Does anyone else agree?

[@ShivamGupta-nz7dy]

L3 is not correct, I think

[@prabhakarshukla6430]

L3 Incorrect

[@ritabrotoganguly5729]

@@prabhakarshukla6430 why?

[@yashshah7546]

for length atleast 2 a+b* should come before a+b^2 also na?

[@Games-ht8yz]

Yes

[@curias7]

for problem number 2 the answer could be just (a+b)*

[@anshjain257]

This would contain strings of length less than 2

[@anirudhyasarkhel8247]

Sir please provide proof for those 2 theorems of Regular languages, imp for exam

[@tiyashadas5247]

Can the regular expression for atmost 2 be (a+b)* ?

[@pratyushkumar3829]

No, because that would include all the strings over the language {a,b}. Meaning (a+b)* would also contain strings of length 3,4,5 and so on

[@fritz6600]

Well, I was wondering it to be (a+b)(a+b)R*

[@quantodedreamer9371]

@@pratyushkumar3829 no it doesnt affect because it is atleast 2.. the problem is (a+b)* also contains null value

[@barnabassolomon1629]

on question 2 why '*' instead of '+' symbol. its not supposed to include epsilon right?

[@dh.418]

Yeah, I had the same doubt, but then I taught myself saying, even if ( a+b) * gives out a E, then end string would be (a+b) (a+b) E ...i.e simply (a+b) (a+b) , so this does not effect the outcome

[@huh_wtf]

At 3:50 (a+b) (a+b)^+ would work right?

[@arisvrazitoulis5274]

No, star could represent e , so in your expression an example could be (a)(e) = a is formed but not accepted because we want at least 2

[@sent4444]

Yes, plus could not represent e

[@MrRaman900]

Sir can you please clarify that why we are doing union in first question(string of length exactly 2).

[@arsha1625]

It's already taught in lecture 46. He taught ,when there are more than one element in the set without an epsilon .do OR operation ,ie; use + sign..that is union 👍

[@prithhviraajchattopadhyay7698]

Can we write (a+b)*2......for Q1?

[@owlietheowl8776]

no we cannot as it is not a valid regular expression.

[@shree2710]

Saurav Kumar omg yws!! Thanks a lot

[@venkateshprasadpatchava7733]

Can we take a out from L1 ...as you said that we can take a out from L3

[@venkateshprasadpatchava7733]

I mean to ask u that u says we can take a from (e+a+b) if it is possible the we can take a out from (a+b) from L1 but the question is that we have to write the regular expressions only that takes exactly 2... That my doubt..

[@ProfessionalTycoons]

Also for the third answer can we write as (a+b)?(a+b)?

[@perikilasujith7175]

no coz u cant represent the null symbol

[@neiljohn2637]

50

[@deepakdeshmukh2013]

(a+ϵ).(b+ba)* : how to write this equation into simple English

[@sinto4105]

(a+b)*

[@prabhasreddymalla4615]

@@sinto4105 explain?

[@degoaty]

I think 3 is should be(€ + a) (€ + b) (a+b) (a+b) isn't it?

[@gabrielpereiramendes3463]

#Excelent!

[@harshaahuja1926]

2:50

[@uselessvader]

Why is it not (a+b)(a+b)^+ for 2 at 3:52 ?

[@HighbrowDirector]

It says at least 2, (a+b)* can be null or more if it's null then we need at least two without * (a+b)(a+b)

[@wel5457]

Why cant we include € in 1 n 2 eg??

[@BlizZarDaSh]

that's because in eg 3 the question was 'atmost 2' which means including no value that is defined as epsilion. 1 and 2 eg does not include no value so no epsilion.

[@entertainclips6006]

For 3 Question could we write (a + b)* - (a +b)(a+b) ?

[@sent4444]

no minus defined

[@asahoo550]

If language accepting at least 2 is an infinite set then how come it will be a regular expression.. It's can't be processed in FSA

[@DnyaneshwarPanchaldsp]

💐💐💐💐👌

[@PomegranateAmazing79]

not very helpful

[@ChristianBurnsShafer]

Either (1) you didn't understand the material, (2) you understand it and think it's useless, or (3) you already knew it and had no purpose watching the video in the first place. If it's the first case, try asking questions. If it's the second case then you're in the wrong field of expertise. If it's the third case then wth are you doing here. In any case you shouldn't just complain like a little fucking kid.

[@S-S445]

Tqsm sir

[@MohamedMahmoud-ul4ip]

3:50