Chương 3 - Ngôn ngữ chính quy và văn phạm chính quy doc
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 (176.26 KB, 23 trang )
NGÔN NGỮ CHÍNH QUY VÀ VĂN
PHẠM CHÍNH QUY
Dr. Huỳnh Trung Hiếu
Faculty of Information Technology
HoChiMinh City University of Industry
2
Regular Languages & Grammars
L is regular iff L = L(M) for some DFA M
Trong chương này, ta sẽ nghiên cứu những cách
khác để biểu diễn ngôn ngữ chính quy.
3
Regular Languages & Grammars
Way of representing Way of thinking
4
Regular Expressions
L = value of E
5
Regular Expressions
Alphabet Σ
1. ∅, λ và a ∈ ∑ là các biểu thức chính quy. Những biểu thức
này gọi là các biểu thức chính qui nguyên tố.
2. Nếu r1 và r2 là các biểu thức chính quy thì r1 + r2, r1 . r2,
r1* và (r1) cũng là các biểu thức chính quy.
3. Một chuỗi gọi là biểu thức chính quy nếu và chỉ nếu nó có
thể được xây dựng từ các biểu thức chính quy nguyên tố bởi
áp dụng một số hữu hạn lần các quy tắc trong mục 2.
Ngôn ngữ liên kết với biểu thức chính quy
Biểu thức chính quy được dùng để
mô tả ngôn ngữ chính qui. Tổng quát,
nếu r là biểu thức chính quy thì ta
nói L(r) là ngôn ngữ được sinh ra từ
r.
7
Ngôn ngữ liên kết với biểu thức chính quy
1. L(∅) = {}
2. L(λ) = {λ}
3. L(a) = {a}
4. L(r
1
+ r
2
) = L(r
1
)∪L(r
2
)
5. L(r
1
. r
2
) = L(r
1
)L(r
2
)
6. L(r
1
*
) = (L(r
1
))
*
7. L((r
1
)) = L(r
1
)
Ngôn ngữ L( r ) được biểu thị bởi bất kì một biểu thức chính quy r nào,
thì được định nghĩa bởi các quy tắc sau.
8
Example 1
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, }
9
Precedence Rules
star-closure > concatenation > union
L(a
*
. a + b)
= L(a
*
. a)∪L(b)
= (L(a
*
) L(a))∪L(b)
= ((L(a))
*
L(a))∪L(b)
= ({λ, a, aa, aaa, }{a})∪{b}
= {a, aa, aaa, , b}
10
Example 2
r = (a + b)
*
(a + bb)
L(r) = ?
11
Example 3
r = (aa)
*
(bb)
*
b
L(r) = ?
12
Example 4
L(r) = {w∈{0, 1}
*
| w có ít nhất 1 cặp số 0 liên tiếp}
r = ?
13
Example 4
L(r) = {w∈{0, 1}
*
| w has at least one pair of consecutive zeros}
r = (0 + 1)
*
00 (0 + 1)
*
14
Example 5
L(r) = {w∈{0, 1}
*
| w has no pair of consecutive zeros}
r = ?
15
Example 5
L(r) = {w∈{0, 1}
*
| w has no pair of consecutive zeros}
r = (1 + 01)
*
(0 + λ)
16
Equivalent Regular Expressions
r
1
and r
2
are equivalent iff L(r
1
) = L(r
2
)
17
Example 6
r
1
= a . (b + c) r
2
= a . b + a . c
L(r
1
) = L(r
2
) = {ab, ac}
18
Homework
Exercises: 1, 4, 5, 6, 7, 13, 23 of Section 3.1 -
Linz’s book.
19
Regular Expressions & Languages
Given a regular expression r, there exists an NFA
that accepts L(r).
20
Regular Expressions & Languages
q
0
q
1
NFA that accepts ∅
q
0
q
1
NFA that accepts {λ}
λ
q
0
q
1
NFA that accepts {a}
a
21
Regular Expressions & Languages
NFA that accepts L(r
1
+ r
2
)
M(r
1
)
M(r
2
)
λ
λ λ
λ
22
Regular Expressions & Languages
NFA that accepts L(r
1
.r
2
)
M(r
1
) M(r
2
)
λ
λ
λ
23
Regular Expressions & Languages
NFA that accepts L(r
1
*
)
M(r
1
)
λ λ
λ
λ
