CS241 Lecture Notes - Lecture 7: Regular Language, Concatenation, Regular Expression
26 May 2018
School
Department
Course
Professor
May 24, 2018
Regular Languages
- Built using finite languages (with 3 different operations)
- allow union of 2 languages: L1 U L2 = {x | x in L1, x in L2}
- allow concatenation: L1.L2 = {xy | x in L1, y in L2|} (sometimes just written as L1L2,
without the dot)
- allow repetition: L* = {(epsilon)} U {xy | x in L*, y in L} - (0 or more)
concatenation ex.
L1 = {dog, cat}
L2 = {fish, (epsilon)}
L1L2 = {dogfish, dog, catfish, cat}
repetition ex.
L = {a,b}
L* = {(epsilon), a, b, aa, ab, ba, bb, ...}
One way of expressing a regular language is to use regular expressions.
Regular Expressions
- 0 -> no words
- (epsilon) -> empty word
- a -> a word just containing symbol a
Concatenation
R1R2 (R1 and R2 are regular expressions)
Words matched by R1 followed by a word matched by R2
Union/Choice/Alternation
R1|R2 (word matched by R1 or R2)
Repetition
R* (0 or more repetitions of words matched by R)
* before .
ex. ab* => a(b*)
. before |
ex. ab|c => (ab)|c
*Note: + and ? are extended regular expressions (we can write them using *, ., |)
a+ => aa*
a? => (epsilon)|a
Document Summary
Built using finite languages (with 3 different operations) Allow union of 2 languages: l1 u l2 = {x | x in l1, x in l2} Allow concatenation: l1. l2 = {xy | x in l1, y in l2|} (sometimes just written as l1l2, without the dot) Allow repetition: l* = {(epsilon)} u {xy | x in l*, y in l} - (0 or more) concatenation ex. L1l2 = {dogfish, dog, catfish, cat} repetition ex. L* = {(epsilon), a, b, aa, ab, ba, bb, } One way of expressing a regular language is to use regular expressions. 0 -> no words (epsilon) -> empty word. A -> a word just containing symbol a. Words matched by r1 followed by a word matched by r2. R* (0 or more repetitions of words matched by r) * before . ex. ab* => a(b*) before | ex. ab|c => (ab)|c. Regular expressions are a convenient shorthand for specifying reg.
