Definition: Let L be a language. L is a regular language (RL) if there exists a regular expression r that
denotes L.
Examples:
r1 = ab + ba denotes L1 = {ab, ba}
r2 = a+b* denotes L2 = {anbm: n ³ 1, m ³ 0}
r3 = ab(a + b)* denotes L3 = {x: ab is prefix of x}
L1, L2, L3
, L4 are
regular languages over S
Denotation: L(r) means the language denoted by r.
Regular Language (RL)
Gist: Every RE denotes a regular language
r4 = (a + b)*ab(a + b)* denotes L4 = {x: ab is substring of x}
5/29