Language.md (878B)
1 # Language 2 3 **Source:** Theory of Computation 4 5 **Lecture:** 2 6 7 **Definition:** A language (alphabet) is a finite set of symbols. 8 9 Examples: 10 11 \Sigma = {0,1} 12 13 \Sigma = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z} 14 15 #### Operations 16 17 We can take the intersection and union of languages because they are simply sets. 18 19 We can also concatenate two languages which is all combinations of elements of the first set followed by an element of the second set. Given this, we see languages are not commutative. 20 21 Given that words can only happen once in a language, the concatenation of two languages is **at most** m * n in size where m is t he size of the first set and n is the size of the second set. 22 23 ### Strings 24 25 #### Definition 26 27 A string over an alphabet is a finite sequence (ordered) of symbols from the alphabet. 28 29 w_1 = 01010010 30 31 w_2 = abracadabra 32 33 \epsilon = empty string