What Is a Language?Regular LanguagesWhat Is a Language?Do Homework 2.Grammars, Languages, and Machines Language L Grammar Accepts MachineStrings: the Building Blocks of LanguagesAn alphabet is a finite set of symbols: English alphabet: {A, B, C, …, Z}Binary alphabet: {0, 1}A string over an alphabet is a finite sequence of symbols drawn from the alphabet.English string: happynewyearbinary string: 1001101We will generally omit “ ” from strings unless doing so would lead to confusion.The set of all possible strings over an alphabet is written *.binary string: 1001101 {0,1}*The shortest string contains no characters. It is called the empty string and is written “ ” or (epsilon).The set of all possible strings over an alphabet is written *.More on StringsThe length of a string is the number of symbols in it.|| = 0|1001101| = 7A string a is a substring of a string b if a occurs contiguously as part of b.aaa is a substring of aaabbbaaaaaaaaa is not a substring of aaabbbaaaEvery string is a substring (although not a proper substring) of itself. is a substring of every string. Alternatively, we can match anywhere.Notice the analogy with sets here.Lecture Notes 2 What is a Language? 1Operations on StringsConcatenation: The concatenation of two strings x and y is written x || y, xy, or xy and is the string formed by appending the string y to the string x. |xy| = |x| + |y|If x = and y = “food”, then xy = If x = “good” and y = “bye”, then |xy| =Note: x = x = x for all strings x.Replication: For each string w and each natural number i, the string wi is defined recursively as w0 = wi = wi-1 w for each i 1Like exponentiation, the replication operator has a high precedence.Examples:a3 = (bye)2 = a0b3 =String ReversalAn inductive definition:(1) If |w| = 0 then wR = w = (2) If |w| 1 then a : w = ua(a is the last character of w) and wR = auRExample:(abc)R = More on String ReversalTheorem: If w, x are strings, then (wx)R = xRwR Example: (dogcat)R = (cat)R(dog)R = tacgodProof (by induction on |x|):Basis: |x| = 0. Then x = , and (wx)R = (w)R = (w)R = wR = RwR = xRwR Induction Hypothesis: If |x| n, then (wx)R = xRwRInduction Step: Let |x| = n + 1. Then x = u a for some character a and |u| = n (wx)R= (w (ua))R= ((wu)a)Rassociativity= a(wu)Rdefinition of reversal= auRwRinduction hypothesis= (ua)RwRdefinition of reversal= xRwRd o g c a t w x u aLecture Notes 2 What is a Language? 2Defining a Language A language is a (finite or infinite) set of finite length strings over a finite alphabet .Example: Let = {a, b} Some languages over : , {}, {a, b}, {, a, aa, aaa, aaaa, aaaaa} The language * contains an infinite number of strings, including: , a, b, ab, ababaaaExample Language DefinitionsL = {x {a, b}* : all a's precede all b's}L = {x : y {a, b}* : x = ya}L = {an, n 0 }L = an (If we say nothing about the range of n, we will assume that it is drawn from N, i.e., n 0.)L = {x#y: x,y {0-9}* and square(x) = y}L = {} = (the empty language—not to be confused with {}, the language of the empty string)Techniques for Defining LanguagesLanguages are sets. Recall that, for sets, it makes sense to talk about enumerations and decision procedures. So, if we want to provide a computationally effective definition of a language we could specify either a Language generator, which enumerates (lists) the elements of the language, or a Language recognizer, which decides whether or not a candidate string is in the language and returns True if it is and False if it isn't.Example: The logical definition: L = {x : y {a, b}* : x = ya} can be turned into either a language generator or a language recognizer.How Large are Languages? The smallest language over any alphabet is . || = 0 The largest language over any alphabet is *. |*| = ?- If = then * = {} and |*| = 1 - If then |*| is countably infinite because its elements can be enumerated in 1 to 1 correspondence with the integers as follows:1. Enumerate all strings of length 0, then length 1, then length 2, and so forth.2. Within the strings of a given length, enumerate them lexicographically. E.g., aa, ab, ba, bb So all languages are either finite or countably infinite. Alternatively, all languages are countable.Operations on Languages 1Normal set operations: union, intersection, difference, complement…Examples: = {a, b} L1 = strings with an even number of a'sL2 = strings with no b'sL1 L2 = L1 L2 = L2 - L1 =( L2 - L1) = Lecture Notes 2 What is a Language? 3Operations on Languages 2Concatenation: (based on the definition of concatenation of strings)If L1 and L2 are languages over , their concatenation L = L1 L2, sometimes L1L2, is{w *: w = x y for some x L1 and y L2}Examples:L1 = {cat, dog} L2 = {apple, pear} L1 L2 = {catapple, catpear, dogapple, dogpear}L1 = {an: n 1} L2 = {an: n 3} L1 L2 = Identities:L = L = L (analogous to multiplication by 0)L{}= {}L = L L (analogous to multiplication by 1)Replicated concatenation:Ln = LLL L (n times)L1 = LL0 = {}Example: L = {dog, cat, fish} L0 = {} L1 = {dog, cat, fish} L2 = {dogdog, dogcat, dogfish, catdog, catcat, catfish, fishdog, fishcat, fishfish}Concatenating Languages Defined Using VariablesL1 = an = {an : n 0} L2 = bn = {bn : n 0} L1 L2 = {an : n 0}{bn : n 0} = { an bm : n,m 0} (common mistake: ) anbn = { an bn : n 0}Note: The scope of any variable used in an expression that invokes replication will be taken to be the entire expression.L = 1n2mL = anbmanOperations on Languages 3Kleene Star (or Kleene closure): L* = {w * : w = w1 w2 … wk for some k 0 and some w1, w2, … wk L}Alternative definition: L* = L0 L1 L2 L3 … Note: L, L*Example: L = {dog, cat, fish} L* = {, dog, cat, fish, dogdog, dogcat, fishcatfish, fishdogdogfishcat, …}Another useful definition: L+ = L L* (L+ is the closure of L under
View Full Document
Unlocking...