we have the first lecture on theory of computation and automata so first of all we need to understand why do we need to subject we why do we need to study this subject so this is basically a theoretical subject but we need this subject if we want to process some textual data and that textual data may be the nature language like english or any other language or maybe some programming language so if you want to write a compiler for some programming language you will definitely need these theories and if you want to write some do some sheet some cross text processing for nature language again you will this this theory will be quite helpful for you so in some way you can say that this course is actually the prerequisite for the compile reconstruction course so this is you know a theoretical course and in compiler construction you implement these theories so the first topic that we are going to discuss in this course is uh regular expansions so regular expression is a way to represent a set of words a language so for i know using regular expressions you can define some rules and all those words which follow those rules are actually called the language for that library expression so before uh you know uh going into detail uh let’s discuss some symbols that we will use in the level expression uh this is a superscript static this symbol means 0 to n it will at least 0 and add max and numbers and and entities and then we see superscript plus sign and this plus sign means 1 to n is at least 1 but there is no upper limit and similarly a simple plus sign and this plus sign will be like r so if you have a list of letters that is separated by this plus sign it means we will choose one letter at a time from the given list of letters so to further understand the sign and symbols let’s see some examples let’s say you have a regular expression a with superscript plus sign so it means here as you know subscript plus sign means at least one but there is no upper limit so all these words all these entities are the you know words of this language so at least one means single a so double a is also low triple a and so on there is no upper limit so this regular expression represent this language and these are the words of this language and similarly next we have a superscript static sound and super static means you know at least zero it means null is also allowed and there is no upper limit so null single a double a triple a and so on so in a way you can say you can conclude from this that a static and a superscript plus signs are uh you know by similar to each other the only difference is that a star a superscript static includes null but a superscript plus does not include null so we can say that a superscript plus sign is equal to a concatenate with a superscript static so because here you can also choose null so if you want to get it because you you make it made later that there will be will be at least single a but there is no upper limit
so to next to understand the concept of this plus sign we see some more examples like here here it we have another expression a plus b so here i already told you that this plus sign means you will pick either a or b so you will pick one letter from the given range of letters so here if you pick a then the word becomes simply a and if you pick b then the word becomes simply b so this regular expression can generate these two words only so these are the words of this language uh next we see another regular expression 1 plus 2 into a plus b so here as i already told that we have to pick just one letter at a time from the level in the flatter so if we pick one from the first set and a from the second set we get one a and if we pick one from the first set and b from the second fret it becomes one b and if we pick two from the first set and a from the second set it becomes two a and even two from the first set and b from the second set it becomes 2b so these are the words of this language and next we have an other regular expression just for the sake of understanding uh a plus b into a plus b so here you can pick item a or b from the first set and either a or b from the second set so the total possible combinations become we have these four possible combinations a a a b b a and b and in the same fashion if you have this double expression then you need to guess how many bars are possible from this then you can say that you can pick uh you have two options here you can pick either a or b two options here and two options here so in total you know two into two so here we have uh you know total eight options so and these are those eight options the possible word that we can generate from this question is triple a a b b a and so on so i am giving you this example just to make you understand that how the words can be generated from the regular expression like this that we have to pick only one letter from the given end of the letters and in this case like if you have standard or plus sign then you definitely have these rules at least one are not too many so next we have some more examples to further elaborate the concept let’s say we have a regular expression like this and this is a very uh common regular expression that you will see in your next lecture so this regular expressions actually means you can say any word that is possible uh from these two letters so you can generate any word from a and b using this type of especially including null so how it is possible so let’s see as we already discussed that superscript static means 0 to n so it means it may be 0 it may be 1 it may be 2 maybe 3 it will be 4 5 6 7 8 and so on so this level efficient means all the regular expressions combined so if we assume that this direct is actually zero it means none we are not including any letter from this idea of letters so we can generate null and if we assume that this static can assume 1 then it means we have these two letters and we can generate these two words only and if we zoom to here that it is equal into a plus b to a plus b and write we saw earlier they can generate these four words and if we assume three here then like we saw earlier it is equivalent to these three uh you know uh a plus b to a plus b a plus and can generate you know these eight letters sorry i it has typing mistake there can you get these eight letters
and so on so from here we conclude that if you see a regular expression like this then you can generate delete any word that is possible from the letters a and b including so and if you see a plus b whole plus sign it is almost same thing the only thing is that that it cannot generate null so the at least you must see at least a single a a single b and then so it is a plus b whole plus sign is equal to a plus b into it must be over static so this is the you know a little introduction to regular expressions and to further uh elaborate this concept to further understand this concept and watch the next video we will see some more samples