Institute Academy

Kleene Star Closure Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ * , is the collection of all strings defined over Σ, including Λ. It is to be noted that Kleene Star Closure can be defined over any set of strings. Examples If Σ = {x} Then Σ * = {Λ, x, xx, xxx, xxxx, ....} If Σ = {0,1} Then Σ * = {Λ, 0, 1, 00, 01, 10, 11, ....} If Σ = {aaB, c} Then Σ * = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, ....} Note Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By infinite language, it is supposed that the language contains infinite many words, each of finite length). Kleen PLUS Operation ( + ) Kleen Plus Operation is same as Kleene Star Closure except that it does not generate Λ (null string), automatically. Example If Σ = {0,1} Then Σ + = {0, 1, 00, 01, 10, 11, ....} If Σ = {aab, c} Then Σ + = {aab, c, aabaab, aabc, caab, cc, ....} Remark It is to be noted that Kleene Star can also be operated on any str

Reverse of a String Definition : The reverse of a string s denoted by Rev(s) or s r , is obtained by writing the letters of s in reverse order. Example If s=abc is a string defined over Σ={a,b,c} then Rev(s) or s r = cba Example Σ= {B, aB, bab, d} s=BaBbabBd Rev(s)=dBbabaBB Defining Languages The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using Regular Expressions(RE) and using Finite Automaton(FA) etc. Descriptive definition of language The language is defined, describing the conditions imposed on its words. Example The language L of strings of odd length, defined over Σ={a}, can be written as L={a, aaa, aaaaa,.....} Example The language L of strings that does not start with a, defined over Σ ={a,b,c}, can be written as L ={L, b, c, ba, bb, bc, ca, cb, cc, ...} Example The language L of strings of length 2, defined over Σ ={0,1,2}, can be written as L={00, 01, 02,10, 11,12,20,21,22} Example The lan

Summary Introduction to the course title, Formal and In-formal languages, Alphabets, Strings, Null string, Words, Validand In-valid alphabets, length of a string, Reverse of a string, Defining languages, Descriptive definition of languages, EQUAL, EVEN-EVEN, INTEGER, EVEN, { a n b n }, { a n b n a n }, factorial, FACTORIAL, DOUBLEFACTORIAL, SQUARE, DOUBLESQUARE, PRIME, PALINDROME. What does automata mean? Definition : It is the plural of automaton, and it means “something that works automatically” Introduction to languages There are two types of languages                     1) Formal Languages (Syntactic languages)                    2) Informal Languages (Semantic languages) Alphabets Definition : A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by Σ ( Greek letter sigma). Example Σ = {a,b} Σ = {0,1} (important as this is the language which the computer understands.) Σ = {i,j,k} Note Certain version of language AL