close

Se connecter

Se connecter avec OpenID

Chapter 11

IntégréTéléchargement
Chapter 11 - 1
Regular Languages
1
Section 11.1 Regular Languages
• Problem: Suppose the input strings to a
program must be strings over the alphabet
{a, b} that contain exactly one substring
bb. In other words, the strings must be of
the form xbby, where x and y are strings
over {a, b} that do not contain bb, x does
not end in b, and y does not begin with b.
In a few minutes, we’ll see how to describe
the strings formally.
2
regular language
• A regular language over alphabet A is a
language constructed by the following
rules:
– Ф and {٨} are regular languages.
– {a} is a regular language for all a ∈ A.
– If M and N are regular language, then so are
M ⋃ N, MN, and M*.
3
Example
• Let A = {a, b}. Then the following
languages are a sampling of the regular
languages over A:
Ф, {٨}, {a}, {b}, {a, b}, {ab}, {a}* = {٨, a, aa,
aaa, …, an, …}.
4
regular expression
• A regular expression over alphabet A is an
expression constructed by the following rules:
– Ф and ٨ are regular expressions.
– a is a regular expression for all a ∈ A.
– If R and S are regular expressions, then so are (R), R
+ S, R•S, and R*.
The hierarchy in the absence of parentheses is, *
(do it first), •, + (do it last).
Juxtaposition will be used in place of •.
5
Example
• Let A = {a, b}. Then the following
expressions are a sampling of the regular
expressions over A:
Ф, ٨, a, b, ab, a + ab, (a + b)*.
6
Regular expressions represent
regular languages
• Regular expressons represent regular
languages by the following correspondence,
where L(R) denotes the regular language of the
regular expression R.
L(Ф) = Ф
L(٨) = {٨},
L(a) = {a} for all a ∈ A,
L(R + S) = L(R) ⋃ L(S),
L(RS) = L(R)L(S),
L(R*) = L(R)*.
7
Example
• The regular expression ab + a* represents
the following regular language:
L(ab + a*) = L(ab) ⋃ L(a*)
= L(a)L(b) ⋃ L(a)*
= {a}{b} ⋃ {a}*
= {ab} ⋃ {٨, a, aa, aaa, …, an, …}
={ab, ٨, a, aa, aaa, …, an, …}.
8
Example
• The regular expression (a + b)* represents the following
regular language:
L((a + b)*) = (L(a + b))* = {a, b}*, the set of all possible
strings over {a, b}.
• Back to the Problem: Suppose the input strings to a
program must be strings over the alphabet {a, b} that
contain exactly one substring bb. In other words, the
strings must be of the form xbby, where x and y are
strings over {a, b} that do not contain bb, x does not end
in b, and y does not begin with b. How can we describe
the set of inputs formally?
• Solution: let x = (a + ba)* and y = (a + ab)*.
9
Quizzes
• Quiz. Find a regular expresson for {abn | n
∈ N} ∪ {ban | n ∈ N}.
• Answer. ab* + ba*.
• Quiz. Use a sentence to describe the
language of (b + ab)*(٨ + a).
• Answer. All strings over {a, b} whose
substrings of a’s have length 1.
10
The Algebra of Regular
Expressions
• Equality: Regular expressions R and S are
equal, written R = S, when L(R) = L(S).
• Examples. a + b = b + a, a + a = a, aa* =
a*a, ab ≠ ba.
11
Properties of +, • and closure
+ is commutative, associative, Ф is identity for +, and R + R = R.
• is associative, ٨ is identity for • and Ф is zero for •
• distributes over +
(closure properties)
Ф* = ٨* = ٨.
R* = R*R* = (R*)* = R + R*.
R* = ٨ + R* = ٨ + RR* = (٨ + R)* = (٨ + R)R*.
R* = (R + R2 + …+ Rk)* = ٨ + R + R2 + …+ Rk-1 + RkR* for any k ≥
1.
R*R = RR*.
(R + S)* = (R* + S*)* = (R*S*)* = (R*S)*R* = R*(SR*)*.
R(SR)* = (RS)*R.
(R*S)* = ٨ + (R + S)*S and (RS*)* = ٨ + R(R + S)*.
Proof: All properties can be verified by showing that the underlying
regular languages are equal as sets. QED.
12
Quizzes
• Quiz. Explain each inequality.
(1). (a + b)* ≠ a* + b*. (2) (a + b)* ≠ a*b*.
• Answers. (1) ab ∈ L((a + b)*) - L(a* + b*).
(2) ba ∈ L((a + b)*) - L(a*b*).
• Quiz. Simplify the regular expression aa(b* + a)
+ a(ab* + aa).
• Answer. aa(b* + a) + a(ab* + aa)
= aa(b* + a) + aa(b* + a) • distributes over +
= aa(b* + a)
R + R = R.
13
Example/Quiz
• Show that (a + aa)(a + b)* = a(a + b)*.
• Proof: (a + aa)(a + b)*
= (a + aa)a*(ba*)*
(R + S)* = R*(SR*)*
= a(٨ + a)a*(ba*)*
R = R٨ and • distributes over +
= aa*(ba*)*
(٨ + R)R* = R*
= a(a + b)*
(R + S)* = R*(SR*)* QED.
14
Example/Quiz
•
•
Show that a*(b + ab*) = b + aa*b*.
Proof: a*(b + ab*)
= (٨ + aa*)(b + ab*)
R* = ٨ + RR*
= b + ab* + aa*b + aa*ab*
• distributes over +
= b + (ab* + aa*ab*) + aa*b
+ is commutative and associative
= b + (٨ + aa*)ab* + aa*b
R = R٨ and • distributes over +
= b + a*ab* + aa*b
R* = ٨ + RR*
= b + aa*b* + aa*b
R*R = RR*
= b + aa*(b* + b)
• distributes over +
= b + aa*b*.
R* = R* + R QED.
15
Example
• Show that a* + abb*a = a* + ab*a.
• Proof: Starting on the RHS, we have
a* + ab*a
= a* + a(٨ + bb*)a
R* = ٨ + RR*
= a* + aa + abb*a
• distributes over +
= (٨ + aa*) + aa + abb*a R* = ٨ + RR*
= ٨ + (aa* + aa) + abb*a + is associative
= ٨ + a(a* + a) + abb*a • distributes over +
= ٨ + aa* + abb*a
R* = R + R*
= a* + abb*a
R* = ٨ + RR* QED.
16
Example
• Show that (a + aa + … + an)(a + b)* = a(a + b)* for all n ≥ 1.
• Proof (by induction): If n = 1, the statement becomes a(a + b)* = a(a
+ b)*, which is true. If n = 2, the statement becomes (a + aa)(a + b)*
= a(a + b)*, which is true by a previous example. Let n > 2 and
assume the statement is true for 1 ≤ k < n. We need to prove the
statement is true for n. The LHS of the statement for n is
(a + aa + … + an)(a + b)*
= a(a + b)* + (aa + … + an)(a + b)*
• distributes over +
= a(a + b)* + a(a + aa + … + an-1)(a + b)*
• distributes over +
= a(a + b)* + aa(a + b)*
induction assumption
= (a + aa)(a + b)*
• distributes over +
= a(a + b)*
induction assumption
The last line is the RHS of the statement for n. So the statement is
true for n. Therefore, the statement is true for all n ≥ 1. QED.
17
Example/Quiz
• Use regular algebra to show that R + (R + S)* = (R + S)*.
• Proof:
R + (R + S)* = R + [٨ + (R + S) + (R + S)(R+ S)*]
R* = ٨ + R +
2
k-1
k
R + ... + R + R R*
= ٨ + (R + R) + S + (R + S)(R+ S)*
+ is associative
= ٨ + R + S + (R + S)(R+ S)*
R+R=R
= ٨ + (R + S) + (R + S)(R+ S)*
+ is associative
= (R+ S)*
R* = ٨ + R + R2 + ... + Rk-1 + RkR*
QED.
• Take-home quiz: Use regular algebra to show that
(a + ab)*a = a(a + ba)*.
18
The End of Chapter 11 -1
19
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
113 Кб
Étiquettes
1/--Pages
signaler