Basic regular expressions The single characters from alphabet matching themselves a matches the character a by writing l(ai a j f denotes the empty string, by l(a=s {}orΦ matches no string at all,byL(Φ)={}
Basic Regular Expressions • The single characters from alphabet matching themselves – a matches the character a by writing L(a)={ a } – ε denotes the empty string, by L(ε)={ε} – {} or Φ matches no string at all, by L(Φ)={ }
Regular Expression Operations Choice among alternatives, indicated by the meta-character Concatenation, indicated by juxtaposition Repetition or closure, indicated by the meta-character
Regular Expression Operations • Choice among alternatives, indicated by the meta-character | • Concatenation, indicated by juxtaposition • Repetition or “closure” , indicated by the meta-character *
Choice Among Alternatives If r and s are regular expressions, then rls is a regular expression which matches any string that is matched either by r or by In terms of languages the language rs is the union of language r and s, or L(rs=Lru(s) A simple example, L(ab=l(au (b=fa, b Choice can be extended to more than one alternative
Choice Among Alternatives • If r and s are regular expressions, then r|s is a regular expression which matches any string that is matched either by r or by s. • In terms of languages, the language r|s is the union of language r and s, or L(r|s)=L(r)UL(s) • A simple example, L(a|b)=L(a)U (b)={a, b} • Choice can be extended to more than one alternative
Concatenation If r and s are regular expression the rs is their concatenation which matches any string that is the concatenation of two strings the first of which matches r and the second of which matches s In term of generated languages the concatenation set of strings s1 s2 is the set of strings of s1 appended by all the strings of S2 a simple example,(a b )c matches ac and bc Concatenation can also be extended to more than two regular expressions
Concatenation • If r and s are regular expression, the rs is their concatenation which matches any string that is the concatenation of two strings, the first of which matches r and the second of which matches s. • In term of generated languages, the concatenation set of strings S1S2 is the set of strings of S1 appended by all the strings of S2. • A simple example, (a|b)c matches ac and bc • Concatenation can also be extended to more than two regular expressions
Repetition The repetition operation of a regular expression, called(Kleene) closure, is written r*, where r is a regular expression The regular expression r matches any finite concatenation of strings. each of which matches r a simple example, a* matches the strings epsilon a. aa. aaa In term of generated language, given a set of s of string, s* is a infinite set union, but each element in it is a finite concatenation of string from S
Repetition • The repetition operation of a regular expression, called (Kleene) closure, is written r*, where r is a regular expression. The regular expression r* matches any finite concatenation of strings, each of which matches r. • A simple example, a* matches the strings epsilon, a, aa, aaa,… • In term of generated language, given a set of S of string, S* is a infinite set union, but each element in it is a finite concatenation of string from S