NANJING UNIVERSITY Regular Expressions Definitions Equivalence to Finite Automata .1
1 Regular Expressions Definitions Equivalence to Finite Automata
效绵鼎 RE's:Introduction Regular expressions describe languages by an algebra. They describe exactly the regular languages. If E is a regular expression,then L(E)is the language it defines. We'll describe RE's and their languages recursively. 2
2 RE’s: Introduction ◼ Regular expressions describe languages by an algebra. ◼ They describe exactly the regular languages. ◼ If E is a regular expression, then L(E) is the language it defines. ◼ We’ll describe RE’s and their languages recursively
效绵鼎 Operations on Languages RE's use three operations:union,concatenation, and Kleene star. The union of languages is the usual thing,since languages are sets. ■Example:{01,111,10{00,01}={01,111,10,00} 3
3 Operations on Languages ◼ RE’s use three operations: union, concatenation, and Kleene star. ◼ The union of languages is the usual thing, since languages are sets. ◼ Example: {01,111,10}{00, 01} = {01,111,10,00}
效绵鼎 Concatenation The concatenation of languages L and M is denoted LM. It contains every string wx such that w is in L and x is in M. Example:{01,111,10}{00,01}={0100,0101, 11100,11101,1000,1001}. 4
4 Concatenation ◼ The concatenation of languages L and M is denoted LM. ◼ It contains every string wx such that w is in L and x is in M. ◼ Example: {01,111,10}{00, 01} = {0100, 0101, 11100, 11101, 1000, 1001}
效绵鼎 Kleene Star If L is a language,then L*,the Kleene star or just “star,”is the set of strings formed by concatenating zero or more strings from L,in any order. ■ L*=LOLLOLLLO... Example:{0,10}*={e,0,10,00,010,100, 1010,..} .5
5 Kleene Star ◼ If L is a language, then L*, the Kleene star or just “star,” is the set of strings formed by concatenating zero or more strings from L, in any order. ◼ L* = {ε} L LL LLL … ◼ Example: {0,10}* = {ε, 0, 10, 00, 010, 100, 1010,…}