Languages, Expressions, Automata

1.0 Languages, Expressions, Automata Alphabet: a finite set, typically a set of symbols. Language: a particular subset of the strings that can be made from the alphabet. ex: an alphabet of digits = {-,0,1,2,3,4,5,6,7,8,9} a language of integers = {0,1,2,...,101,102,103,...,-1,-2,etc.} Note that strings such as 2-20 would not be included in this language. Regular Expression: A pattern that generates (only) the strings of a desired language. It is made up of letters of the language’s alphabet, as well as of the following special characters: ( ) ( C + ë used for grouping repetition concatenation (usually omitted) denotes a choice (“or”). a special symbol denoting the null string Precedence from highest to lowest: () ( C + formal (recursive) definition: If A is an alphabet, and a 0 A , then a is a regular expression. ë is a regular expression. If r and s are regular expressions, then the following are also regular expressions: r* , r C s = rs , r + s , and ( r ) examples: (assume that A = {a, b} ) a C b C a (or just aba ) ab + ba b* b(a + ba*)*a (b + ë) matched only by the string aba matched by exactly two strings: ab and ba matched by { ë, b, bb, bbb, ....} matched by bbaaab, and many others Some convenient extensions to regular expression notation: aa = a2, bbbb = b4, etc. a+ = aCa* = { any string of a's of positive length, i.e. excludes ë } ex: (ab)2 = abab a2 b2 , so don't try to use "algebra”. ex: (a+b)2 = (a+b)(a+b) = aa or ab or ba or bb. ex: (a+b)* any string made up of a’s and b’s. Examples of regular expressions over {a, b} : C all strings that begin with a and end with b a (a + b)* b C all non empty strings of even length (aa + ab + ba + bb)+ C all strings with at least one a (a + b)* a (a + b)* C all strings with at least two a's (a + b)* a (a + b)* a (a + b)* C all strings of one or more b's with an optional single leading a (a + ë) b+ C the language { ab, ba, abaa, bbb } ab + ba + abaa + bbb ab (ë + aa) + b (a + bb) (a + bb) b + (b + aba) a or or or? Tips: Check the simplest cases Check for “sins of omission” (forgot some strings) Check for “sins of commission” (included some unwanted strings) More examples Find a regular expression for the following sets of strings on { a, b }: C All strings with at least two b’s. (a + b)* b (a + b)* b (a + b)* C All strings with exactly two b’s. a* b a* b a* C All strings with at least one a and at least one b. (a + b)* (ab + ba) (a + b)* C All strings which end in a double letter (two a’s or two b’s). (a + b)* (aa + bb) C All strings of even length (includes 0 length). (aa + bb + ab + ba)* Finite Automata: a particular, simplified model of a computing machine, that is a “language recognizer”: yes text “recognizer” no aaba A finite automaton (FSA) has five pieces: 1. 2. 3. 4. 5. S A Si Y F = a finite number of states, = the alphabet, = the start state, = one or more final or “accept” states, and = a transition function (mapping) between states, F: S x A º S. The transition function F is usually presented in one of two ways: • as a table (called a transition table), or • as a graph (called a transition diagram). Transition Table (example): A= { a, b }, S = { s0 , s1 , s2 }, Si = s1, Y = { s0 , s2 } current input current state F a b s0 s0 s2 s1 s1 s0 s2 s0 s0 gives the next state < Transition Diagram (example): Note that this FSA is: • Complete (no undefined transitions) • Deterministic (no choices) “Skeleton Method” - a useful solution technique in limited cases: • • • The “skeleton” is a sequence of states assuming legal input. Construct the skeleton, presume that no additional states will be needed. The FSA must be complete and deterministic: for A= { a,b }, every state has exactly two arcs leaving it, one labeled “a” and one labeled “b”. example (skeleton): All strings containing abaa Examples Assume A= { a, b }. Construct the following automata which: 1. Accepts strings of the form (a+b)* start a, b s0 2. Accepts ë only. a, b start a, b s1 s0 3. Accepts strings which begin with a a start a, b s1 s0 s0 start b s1 a found at begin. s2 starting b s2 a, b 4. Accepts strings containing ‘aa’ (skeleton method) a start a s1 s0 b b a, b s2 5. All words containing at least two a's a start a b b All words containing exactly two a's a start a no ‘a’ found one ‘a’ found two ‘a’ found too many ‘a’ b s2 s1 s0 b s0 s1 s2 s3 s2 s1 s0 4. a, b b a s3 a, b Equivalence of Regular Expressions and Finite-State Automata 1. For every regular expression “R”, defining a language “L”, there is a FSA “M” recognizing exactly L. 2. For every FSA “M”, recognizing a language “L”, there is a regular expression “R” matching all the strings of L and no others. (we will prove this later) Question: is there a FSA that can recognize { ë, ab, aabb, aaabbb, . . . } ?? Answer: No, because we need to “remember” how many a’s have been seen to verify that there are as many b’s. Since an FSA can only have a finite number of states there cannot be enough states to count the a’s. We need a more powerful kind of recognizer... that is, a grammar.