Regular Language and Regular Grammar
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (146.05 KB, 50 trang )
Regular Language and
Regular Grammar
Objectives
•
Regular Expression and Regular Language
•
Regular Expression vs Regular Language
•
Regular Grammar
Regular Expression
Alphabet Σ
1.
∅, λ, a∈Σ are regular expressions (known as primitive regular
expressions).
2.
If r1 and r2 are regular expressions,
so are r1 + r2, r1 . r2, r1
*
, and (r1).
Operator Precedence
•
parentheses
•
star-closure (*)
•
concatenation (.)
•
union (+)
Languages Associated with
Regular Expressions
•
Each regular expression stands for a set of strings of symbols in
Σ
each regular
expression represents a language, called
regular language
•
r L(r)
Example 3.1
•
L(a) = {a}
•
L((a + b.c)* ) = {λ, a, bc, aa, abc, bca, bcbc, aaa, aabc, }
•
L(
a
+
b
+) syntax error
Regular Languages
1.
L(∅) = {}
2.
L(λ) = {λ}
3.
L(a) = {a}
4.
L(r1 + r2) = L(r1)∪L(r2)
5.
L(r1 . r2) = L(r1)L(r2)
6.
L(r1
*
) = (L(r1))
*
7.
L((r1)) = L(r1)
Example 3.2
L(a
*
. (a + b))
= L(a
*
) L(a + b)
= (L(a))
*
(L(a)∪L(b))
= {λ, a, aa, aaa, }.{a, b}
= {a, aa, aaa, , b, ab, aab, }
Example 3.3
r = (a + b)
*
(a + bb)
L(r) = ?
Example 3.3
r = (a + b)
*
(a + bb)
L(r) = {w| w ends with a or bb}
Example 3.5
r = (aa)
*
(bb)
*
b
L(r) = ?
Example 3.5
r = (aa)
*
(bb)
*
b
L(r) =
{
a
2
n
b
2
m
+1
:
n
≥ 0,
m
≥ 0}
Example 3.6
L(r) = {w∈{0, 1}
*
| w has at least one pair of consecutive zeros}
r =?
Example 3.6
L(r) = {w∈{0, 1}
*
| w has at least one pair of consecutive zeros}
r = (0 + 1)
*
00 (0 + 1)
*
Example 3.7
L(r) = {w∈{0, 1}
*
| w has no pair of consecutive zeros}
r = ?
Example 3.7
L(r) = {w∈{0, 1}
*
| w has no pair of consecutive zeros}
r = (1 + 01)
*
(0 + λ)
Equivalent Regular Expression
r1 and r2 are equivalent iff L(r1) = L(r2)
Example 3.8
r1 = a . (b + c) r2 = a . b + a . c
L(r1) = L(r2) = {ab, ac}
Regular Expressions and
Languages
Given a regular expression r, there exists an NFA that accepts L(r)
L(r) is a regular language
Primitive NFAs
q
0
q
1
NFA that accepts ∅
q
0
q
1
NFA that accepts {λ}
λ
q
0
q
1
NFA that accepts {a}
a
Primitive NFAs (cont’d)
NFA that accepts L(r
1
+ r
2
)
M(r
1
)
M(r
2
)
λ
λ λ
λ
Primitive NFAs (cont’d)
M(r
1
) M(r
2
)
λλ λ
Primitive NFAs (cont’d)
M(r
1
) M(r
2
)
λλ λ
Primitive NFAs (cont’d)
NFA that accepts L(r
1
*
)
M(r
1
)
λ λ
λ
λ
Example 3.9
b
λ
b bλ
λ
λ
λ
λ
a
λ
λ
λ
λ
a
λ
λ
λ
λ
λ
λ
λ
λ
λ
λ
r = (a + bb)*(ba* + λ)
