CMSC 330: Organization of Programming Languages Regular Expressions and Finite Automata CMSC 330 2 The Theory Behind r.e.’s •! That’s it for the basics of Ruby –! If you need other material for your project, you’ll either see it in discussion section, or you’ll need to learn it on your own •! Next up: How do r.e.’s really work? –! Mixture of a very practical tool (string matching with r.e.’s) and some nice theory –! A great computer science result CMSC 330 3 A Few Questions about Regular Expressions •! What does a regular expression represent? –! Just a set of strings •! What are the basic components of r.e.'s? –! E.g., we saw that e+ is the same as ee* •! How are r.e.'s implemented? –! We’ll see how to turn a r.e. into a program •! Can r.e.'s represent all possible languages? –! The answer turns out to be no! –! The languages represented by regular expressions are called, appropriately, the regular languages CMSC 330 4 Some Definitions •! An alphabet is a finite set of symbols –! Usually denoted ! •! A string is a finite sequence of symbols from ! –! " is the empty string ("" in Ruby) –! |s| is the length of string s •! |Hello| = 5, |"| = 0 –! Note: Ø is the empty set (with 0 elements); Ø # { " } •! Concatenation is indicated by juxtaposition –! If s1 = super and s2 = hero, then s1s2 = superhero –! Sometimes also written s1$s2 –! For any string s, we have s" = "s = sCMSC 330 5 Languages •! A language is a set of strings over an alphabet •! Example: The set of phone numbers over the alphabet ! = {0, 1, 2, 3, 4, 5, 6, 7, 9, (, ), -} –! Give an example element of this language –! Are all strings over the alphabet in the language? –! Is there a Ruby regular expression for this language? •! Is the Ruby regular expression over the same alphabet? •! Example: The set of all strings over ! –! Often written !* CMSC 330 6 Languages (cont’d) •! Example: The set of all valid Ruby programs –! Is there a Ruby regular expression for this language? •! Example: The set of strings of length 0 over the alphabet ! = {a, b, c} –! {s | s ! !* and |s| = 0} = {"} # Ø CMSC 330 7 Operations on Languages •! Let ! be an alphabet and let L, L1, L2 be languages over ! •! Concatenation L1L2 is defined as –! L1L2 = {xy | x ! L1 and y ! L2} –! Example: L1 = {“hi”, “bye”}, L2 = {“1”, “2”} •! L1L2 = {“hi1”, “hi2”, “bye1”, “bye2”} •! Union is defined as –! L1!L2 = { x | x ! L1 or x ! L2} –! Example: L1 = {“hi”, “bye”}, L2 = {“1”, “2”} •! L1!L2 = {“hi”, “bye”, “1”, “2”} CMSC 330 8 Operations on Languages (cont’d) •! Define Ln inductively as –! L0 = {"} –! Ln = LLn-1 for n > 0 •! In other words, –! L1 = LL0 = L{"} = L –! L2 = LL1 = LL –! L3 = LL2 = LLL –! ...CMSC 330 9 Examples of Ln •! Let L = {a, b, c} •! Then –! L0 = {"} –! L1 = {a, b, c} –! L2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc} CMSC 330 10 Operations on Languages (cont’d) •! Kleene closure is defined as L* = !i ![0..%] Li •! In other words... L* is the language (set of all strings) formed by concatenating together zero or more strings from L CMSC 330 11 Definition of Regexps •! Given an alphabet !, the regular expressions over ! are defined inductively as –! ... regular expression denotes language Ø Ø " {"} each element & ! ! {&} CMSC 330 12 Definition of Regexps (cont’d) •! Let A and B be regular expressions denoting languages LA and LB, respectively •! There are no other regular expressions for ! •! We use ()’s as needed for grouping regular expression denotes language AB LALB (A|B) LA!LB A* LA*CMSC 330 13 The Language Denoted by an r.e. •! For a regular expression e, we will write [[e]] to mean the language denoted by e –! [[a]] = {a} –! [[(a|b)]] = {a, b} •! If s![[re]], we say that re accepts, describes, or recognizes s. CMSC 330 14 Example 1 •! All strings over ! = {a, b, c} such that all the a’s are first, the b’s are next, and the c’s last –! Example: aaabbbbccc but not abcb •! Regexp: a*b*c* –! This is a valid regexp because... –! a is a regexp ([[a]] = {a}) –! a* is a regexp ([[a*]] = {", a, aa, ...}) –! Similarly for b* and c* –! So a*b*c* is a regular expression CMSC 330 15 Which Strings Does a*b*c* Recognize? aabbbcc Yes; aa ! [[a*]], bbb ! [[b*]], and cc ! [[c*]], so entire string is in [[a*b*c*]] abb Yes, abb = abb", and " ! [[c*]] ac Yes " Yes aacbc No abcd No -- outside the language CMSC 330 16 Example 2 •! All strings over ! = {a, b, c} •! Regexp: (a|b|c)* •! Other regular expressions for the same language? –! (c|b|a)* –! (a*|b*|c*)* –! (a*b*c*)* –! ((a|b|c)*|abc) –! etc.CMSC 330 17 Example 3 •! All whole numbers containing the substring 330 •! Regular expression: (0|1|...|9)*330(0|1|...|9)* •! What if we want to get rid of leading 0’s? •! ( (1|...|9)(0|1|...|9)*330(0|1|...|9)* | 330(0|1|...|9)* ) •! Any other solutions? •! What about all whole numbers not containing the substring 330? –! Is it recognized by a regexp? CMSC 330 18 Example 4 •! What language does (10|0)*(10|1)* denote? –! (10|0)* •! 0 may appear anywhere •! 1 must always be followed by 0 –! (10|1)* •! 1 may appear anywhere •! 0 must always be preceded by 1 –! Put together, all strings of 0’s and 1’s where every pair of adjacent 0’s precedes any pair of adjacent 1’s CMSC 330 19 What Strings are in (10|0)*(10|1)* ? 00101000 110111101 First part in [[(10|0)*]] Second part in [[(10|1)*]] Notice that 0010 also in [[(10|0)*]] But remainder of string is not in [[(10|1)*]] 0010101 Yes 101 Yes 011001 No CMSC 330 20 Example 5 •! What language does this regular expression recognize? –!( (1|")(0|1|...|9) | (2(0|1|2|3)) ) : (0|1|...|5)(0|1|...|9) •! All valid times written in 24-hour format –! 10:17 –! 23:59 –! 0:45 –! 8:30CMSC 330 21 Two More Examples •! (000|00|1)* –! Any string of 0's and 1's with no single 0’s •! (00|0000)* –! Strings with an even number of 0’s –! Notice that some strings can be accepted more than one way •! 000000 = 00$00$00 = 00$0000 = 0000$00 CMSC 330 22 Regular Languages •! The languages that can be described using regular expressions are the regular languages or regular sets •! Not all languages are regular –! Examples (without proof): •! The set of palindromes over ! •! {anbn
View Full Document
Unlocking...