FIT2014 Lecture Notes - Lecture 5: Kleene Star, Regular Expression, Recursive Definition
28 Jun 2018
School
Department
Course
Professor
Lecture 5 Regular Expression
Regular Expression for Small Languages
Language φ with no words:
Language ε consisting only of the empty word:
Language { w } consisting only of the single word w : w
E.g.: the language {abbab} consisting only of the single word abbab : abbab
Groupings
Grouping are indicated by ()
e.g. ((ab ∪ ba)(e ∪ g) is a regular expression for: {abe, abg, bae, bag}
This use the principle that is
R1 is a regular expression for language L1 and
R2 is a regular expression for language L2, then:
the concatenation R1R2 is regular expression for the language. { x1x2 : x1 is in L1 and x2 is in L2 }
Finite Language consist of finite number of words.
Kleene Star
- Zero or more times is indicated by *
Parse Tree
Important:
1. ε and φ are regular expressions
2. All letters in the alphabet are regular expressions.
3. If R and S are regular
expressions, then so are: (i) (R) (ii) RS (iii) R ∪ S (iv) R*
This is an example of an inductive definition, also known as a recursive definition.
Document Summary
La(cid:374)guage co(cid:374)sisti(cid:374)g o(cid:374)l(cid:455) of the e(cid:373)pt(cid:455) word: Language { w } consisting only of the single word w : w. : the language {abbab} consisting only of the single word abbab : abbab. Grouping are indicated by () e. g. ((ab ba)(e g) is a regular expression for: {abe, abg, bae, bag} R1 is a regular expression for language l1 and. R2 is a regular expression for language l2, then: the concatenation r1r2 is regular expression for the language. { x1x2 : x1 is in l1 and x2 is in l2 } Finite language consist of finite number of words. Zero or more times is indicated by * Important: a(cid:374)d are regular e(cid:454)pressio(cid:374)s, all letters in the alphabet are regular expressions, if r and s are regular expressions, then so are: (i) (r) (ii) rs (iii) r s (iv) r* This is an example of an inductive definition, also known as a recursive definition.
