Tham khảo bài thuyết trình 'bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - chương 3', kỹ thuật - công nghệ, điện - điện tử phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
YOMEDIA/
Chủ đề:
Nội dung Text: Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 3
- Chương 3 Ngôn ngữ chính qui và văn
phạm chính qui
3.1 Biểu thức chính qui (Regular Expression)
3.2 Mối quan hệ giữa BTCQ và ngôn ngữ chính qui
3.3 Văn phạm chính qui (Regular Grammar)
Trang 97
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Biểu thức chính qui
Biểu thức chính qui (BTCQ) là gì?
Là một sự kết hợp các chuỗi kí hiệu của một bảng chữ cái ∑
nào đó, các dấu ngoặc, và các phép toán +, ., và *. trong đó
phép + biểu thị cho phép hội, phép . biểu thị cho phép kết nối,
phép * biểu thị cho phép bao đóng sao.
Ví dụ
Ngôn ngữ {a} được biểu thị bởi BTCQ a.
Ngôn ngữ {a, b, c} được biểu thị bởi BTCQ a + b + c.
Ngược lại BTCQ (a + b.c)* biểu thị cho ngôn ngữ {λ, a, bc, aa,
abc, bca, bcbc, aaa, aabc, ...}.
Trang 98
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Định nghĩa hình thức BTCQ
Định nghĩa 3.1
Cho ∑ là một bảng chữ cái, thì
1. ∅, λ, và a ∈ ∑ tất cả đều là những BTCQ hơn nữa chúng được
gọi là những BTCQ nguyên thủy.
2. Nếu r1 và r2 là những BTCQ, thì r1 + r2, r1. r2, r1*, và (r1) cũng
vậy.
3. Một chuỗi là một BTCQ nếu và chỉ nếu nó có thể được dẫn
xuất từ các BTCQ nguyên thủy bằng một số lần hữu hạn áp
dụng các quy tắc trong (2).
Ví dụ
Cho ∑ = {a, b, c}, thì chuỗi (a + b.c)*.(c + ∅) là BTCQ, vì nó
được xây dựng bằng cách áp dụng các qui tắc ở trên. Còn (a + b
+) không phải là BTCQ.
Trang 99
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Ngôn ngữ tương ứng với BTCQ
Định nghĩa 3.2
Ngôn ngữ L(r) được biểu thị bởi BTCQ bất kỳ là được định
nghĩa bởi các qui tắc sau.
1. ∅ là BTCQ biểu thị tập trống,
2. λ là BTCQ biểu thị {λ},
3. Đối với mọi a ∈ ∑, a là BTCQ biểu thị {a},
Nếu r1 và r2 là những BTCQ, thì
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))*.
Trang 100
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Ngôn ngữ tương ứng với BTCQ (tt)
Qui định về độ ưu tiên
Độ ưu tiên của các phép toán theo thứ tự từ cao đến thấp là
1. bao đóng – sao,
2. kết nối,
3. hội.
Ví dụ
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, . . .}
Trang 101
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Xác định ngôn ngữ cho BTCQ
Tìm ngôn ngữ của các BTCQ sau
r1 = (aa)*(bb)*b
r2 = (ab*a + b)*
r3 = a(a + b)*
Kết quả
L(r1) = {a2nb2m+1: n ≥ 0, m ≥ 0}
L(r2) = {w ∈ {a, b}*: na(w) chẵn}
L(r3) = {w ∈ {a, b}*: w được bắt đầu bằng a}
Trang 102
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Tìm BTCQ cho ngôn ngữ
Tìm BTCQ cho các ngôn ngữ sau
L1 = {tập tất cả các số thực của Pascal}
L2 = {w ∈ {0, 1}*: w không có một cặp số 0 liên tiếp nào}
L3 = {w ∈ {0, 1}*: n0(w) = n1(w)}
Kết quả
r1 = (‘+’ + ‘-’ + λ)(0 + 1 + … + 9)+(‘.’ (0 + 1 + … + 9)+ + λ)
(‘E’ (‘+’ + ‘-’ + λ)(0 + 1 + … + 9)+ + λ)
r2 = [(1* 011*)* + 1*] (0 + λ) hoặc (1 + 01)* (0 + λ)
Không tồn tại BTCQ biểu diễn cho L3
Trang 103
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Một số phép toán mở rộng
Phép chọn lựa r? hoặc [r]
r ? = [r] = (r + λ)
Phép bao đóng dương +
r+ = r.r*
Chú ý
(r*)* = r*
(r1* + r2)* = (r1 + r2)*
(r1r2* + r2)* = (r1 + r2)*
Trong một số tài liệu phép cộng (+) được kí hiệu bằng dấu |
thay cho dấu + . Chẳng hạn (a + b).c thì được viết là (a | b).c
Trang 104
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- BTCQ biểu thị NNCQ
Định lý 3.1
Cho r là một BTCQ, thì tồn tại một nfa mà chấp nhận L(r). Vì
vậy, L(r) là NNCQ.
Bổ đề
Với mọi nfa có nhiều hơn một trạng thái kết thúc luôn luôn có
một nfa tương đương với chỉ một trạng thái kết thúc.
qf1
qf1 λ
tương đương
với qf
λ
qfn
qfn
Trang 105
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Thủ tục: re-to-nfa
Từ bổ đề trên mọi nfa có thể được biểu diễn bằng sơ đồ
như sau
M
qf
q0
Chứng minh
Thủ tục: re-to-nfa
Input: Biểu thức chính qui r.
Output: nfa M = (Q, Σ, δ, q0, F).
B1. Xây dựng các nfa cho các BTCQ nguyên thủy
λ a
q0
q0 q1 q1
q0 q1
(a) nfa chấp nhận ∅ (b) nfa chấp nhận {λ} (c) nfa chấp nhận {a}
Trang 106
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Thủ tục: re-to-nfa (tt)
B2. Xây dựng các nfa cho các BTCQ phức tạp
nfa cho BTCQ r1 + r2
M(r1)
qf1
q01 M(r1)
λ
λ
hoặc
M(r2)
λ λ M(r2)
qf2
q02
ĐK:
1. Không có cạnh đi vào q01 và q02
2. Không có cạnh đi ra qf1 và qf2
Trang 107
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Thủ tục: re-to-nfa (tt)
nfa cho BTCQ r1r2
M(r1) M(r2) λ
λ λ
qf1 qf2
q01 q02
hoặc
M(r1) M(r2)
ĐK:
1. Không có cạnh đi ra qf1 hoặc
2. Không có cạnh đi vào q02
Trang 108
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Thủ tục: re-to-nfa (tt)
nfa cho BTCQ r*
M(r)
λ
M(r)
λ λ
q0≡ qf
hoặc
q0 qf
λ
ĐK:
1. Không có cạnh đi vào q0
2. Không có cạnh đi ra qf
Trang 109
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Ví dụ
Xây dựng nfa cho BTCQ sau
r = (a + bb)*(ba* + λ)
λ
a
λ λ
λ λ
λ
b b
λ λ
λ
λ
λ
λ
λ λ
Hoặc theo a
a λ
λ λ
a
b
phương pháp λ λ
λ λ
b
cải tiến
λ
b
b
Trang 110
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Bài tập BTCQ
Xây dựng nfa cho các BTCQ sau
r1 = aa* + aba*b*
r2 = ab(a + ab)* (b + aa)
r3 = ab*aa + bba*ab
r4 = a*b(ab + b)*a*
r5 = (ab* + a*b)(a + b*a)* b
r6 = (b + a*)(ba* + ab)*(b*a + ab)
Trang 111
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- BTCQ cho NNCQ
Đồ thị chuyển trạng thái tổng quát (generallized transition
graphs):
Là một ĐTCTT ngoại trừ các cạnh của nó được gán nhãn bằng
các BTCQ.
Ngôn ngữ được chấp nhận bởi nó là tập tất cả các chuỗi được
sinh ra bởi các BTCQ mà là nhãn của một con đường nào đó đi
từ trạng thái khởi đầu đến một trạng thái kết thúc nào đó của
ĐTCTT tổng quát (ĐTCTTTQ).
Trang 112
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Đồ thị chuyển trạng thái tổng quát
a* c*
Hình bên biểu diễn một ĐTCTTTQ.
a+b
NN được chấp nhận bởi nó là L(a*(a + b)c*)
Nhận xét
ĐTCTT của một nfa bất kỳ có thể được xem là ĐTTCTTTQ
nếu các nhãn cạnh được diễn dịch như sau.
Một cạnh được gán nhãn là một kí hiệu đơn a được diễn dịch thành cạnh
được gán nhãn là biểu thức a.
Một cạnh được gán nhãn với nhiều kí hiệu a, b, . . . thì được diễn dịch
thành cạnh được gán nhãn là biểu thức a + b + . . .
Mọi NNCQ đều ∃ một ĐTCTTTQ chấp nhận nó. Ngược lại,
mỗi NN mà được chấp nhận bởi một ĐTCTTTQ là chính qui.
Trang 113
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Rút gọn trạng thái của ĐTCTTTQ
Để tìm BTCQ cho một ĐTCTTTQ ta sẽ thực hiện quá trình rút
gọn các trạng thái trung gian của nó thành ĐTCTTTQ tương
đương đơn giản nhất có thể được.
Trạng thái trung gian
Là trạng thái mà không phải là trạng thái khởi đầu, cũng không
phải là trạng thái kết thúc.
Rút gọn trạng thái ce*b
e ae*d
trung gian q. ae*b
b
a
q
qi qj qi qj
d c ce*d
Trang 114
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Định lý
Rút gọn trạng thái q của ĐTCTT sau (a+b)a
q1 ab
a aa q
b1
+b +b)
a a (a
b
aa+b
λ
q0 q q0
a+b
b a+
a b
b ab
q2 q2
Định lý 3.2 a
Cho L là một NNCQ, thì tồn tại một BTCQ r sao cho L = L(r).
r4
r1
r2
Đồ thị chuyển
qf
r3 r = r1*r2(r4 + r3r1*r2)*
q0
trạng thái
Trang 115
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
- Ví dụ
Xác định BTCQ cho nfa sau
a, b b+ab*a a+b
b
b
a
b ab*b
q0 q1 q2 q0 q2
a
r = (b + ab*a)* ab*b(a + b)*
Trang 116
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
