Regular Expressions
Language
Human using complex systems of language Examples :
capacity for acquiring and communication , and a
is
any specific example of such a system
.
Gab ,
aa , ba , bby
In mathematics , computer science and linguistics a Eb aa aba, cbc, abobal
, formal language consists of words whose letters ,
, ,
taken from an alphabet and are well-formed according to a specific set of rules.
are
Sa ,
ab , abb , abbb, ...
3
Formal Language
Symbols Alphabet Word (or strings
concatenation with
· a
,
b, c, 0 ,
1 [a
·
,
b,
ch ·
abc , ana bbbbbca , a,
·
abc .
e = abc
, empty word
· r , 9, ·
40 , 13 · abc . bc =
abobes concatenation
·
(a) = aa
11 Caba)
· = abaaba aba
·
,
·
E < empty word
⑧
11 (
· red , green ,
blue
Now languages from old (set theory ( Kloone Star
Sab babuda , , by =
Sa ,
b , ab , bay L . La = (s t . s th , t t(z] ↳* =
(5 32
, ...
Sn nEIN
,
Sitt for all 0 bi
In]
2
lab , bay e gab by ,
=
(ab] ↳ =
L L .
** =
(2) =
10
3
Cab bas sab by =
[ba) ↳ = W L L .
.
, ,
L =
u(E) L Lu = L d h . .
... L
-
n times
Examples
[ = (a b, c) alphabet For given alphabet [we define language L( *)
,
a can a
such that
Lo =
(a , b)
Li =
Laa ,
ab
,
ac
,
ba bb , be ca ob
, , , , ] L( E) =
[7 ,
X2 ... In nEIN , Vie for all 0<i < n]
ha = Lo Lo . =
Gaa ,
ab , ba , bby
Le =
[V x ,
...
En neI
,
ne3
,
i ] all the words that are a
sequence on n characters such that
u is natural number and less than equal to
Sa is
a n or 3 and
=
,
bab , a
,
b
, c, a ,
...
] &i is in the alphabet I .
↳ G =
my ↳ Gha
ha = Cave ...
In NEI
,
Vie I ] < all the words that are a
sequence on n characters and
· xplicitely start with an 'a' Such thata is a natural number and
= Sabc , ada
,
aba
, a
,
...
Y &i is in the alphabet I .
↳ nhn = Saa ,
ab , acs
↳ (n = (ba ,
bb
,
bc , ca
,
(b
, <)
Li =
Slab)"nEIN] all the words that are a sequence of 'ab' concatenated to itself
n times such that n is a natural number
.
=
[2 ,
ab
,
abab
,
ababab
, ....
Regular Expressions
Definition 1: Let I be an alphabet. A pattern or
regular expression over I is any word over
Examples
Joat = v (0 ,
3
,, *, ( , 13 Operators > [0 ,
2
,
X
, 1 ,
*
]
*
generated by the
following recursive definition .
· I =
(a by , (a(b)
Empty pattern : The character I is a pattern
·
I = (a , b, 2) ((alb) (c) or (a)(b(c)) or
Calblc)
Empty word : The character a is a pattern
Letters : Every letter from I is a pattern
Concatenation : if p , and pe are patterns then so is (pipe)
Alternative If :
p, and pe are patterns then so is (p /Pc)
,
if pattern then (p )
*
Kleene star : p is a so is
, Matching
Definition 2: Let p
be a pattern over an alphabet [ and let s be a word over I . We Examples :
say thats matches p if one of the following cases holds :
I (a
=
,
b, c)
Empty word : the pattern is
e and s is the empty word & Regular Expression : a
,
(ba) *
Base case : the pattern p = z
for a character o from 7 and s = x
· aba >
so it matches
Concatenation : the pattern p is a concatenation (P P2) ,
and there are words
·
aga >
aaa
Wh
So it does not matches
S, and se such that s, matches pi , Se matches P2 and aa a
ww
S is the concatenation of 5, and S2
Alternative : the pattern p is an alternative p =
(pilpe) and s matches Regular Expression : (abIbc) ,)
p, or
P2 (it is allowed to match both) abc
· >
abih
so it does not matches
Kleene the pattern the
Tabl
star : p is in form p =
(q ) *
ands can be
written as a
finite concatenation S = S. S2 ...
In such that
· bea, so it matches
5
. Se
, .... In q ; this includes the
all match case where
S is empty (and thus an empty concatenation ,
with n = 0
Regular Expressions define Languages Regular Language
Definition 3: Let p be a
regular expression over an alphabet
F
. The language defined Definition 4: A language L is regular if it is the set of all words matching some regular
I that match expression, that p such that C <(p)
by pattern p , L(p) is the set of all words over p. . In is
, if there is a pattern =
other words :
*
↓ (p) =
[st s matches
py Examples
Lo = [E, a
,
aa
, ana
,
aaaa
,
...
Y
Examples All of the words of to can be matched by the pattern a *
L(0) I ① So Lois a
regular language
L(E) = (2)
L(x) =
[v] for >E I ↳ =
[2 ,
ab abab ababab
, , , ....
< (pipa) <(p1) <(Pa) All of the words
of L , be matched by the
*
pattern (ab)
=
can
·
h (pipe) <(p) Lipa) So L,
= v is a
regular language
*
h (px) = (h(p))
h =
(a b) ,
All of the words of Le can be matched by the pattern (alb) and (bla)
So
La is a
regular language
↳y =
Sac , bab
All of the words of La can be matched by the pattern (alb)(
SoLy is a
regular language
La =
GW ,
wa , wa
, . . ., Way
All of the words ofIn matched by the pattern (w lwalwal
can be , ...
(Wn)
La
So is a
regular language.
