Ngôn ngữ hình thức và otomat

Giáo trình Kiến trúc máy tính và Hệ điều hành
1
NGÔN NGỮ HÌNH THỨC & ÔTÔMÁT
Giáo trình Kiến trúc máy tính và Hệ điều hành
2
Mục tiêu giáo trình
Cung cấp những kiến thức cơ bản về ngôn ngữ, văn phạm và ôtômát.
Cung cấp các phương pháp phân tích từ vựng, phân tích cú pháp.
Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình.
Rèn luyện kỹ năng lập trình cho sinh viên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giới thiệu
Giáo trình Kiến trúc máy tính và Hệ điều hành
3
Nội dung giáo trình
CHƯƠNG 1. MỞ ĐẦU
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
CHƯƠNG 3. BIỂU THỨC VÀ VĂN PHẠM CHÍNH QUI
CHƯƠNG 4. VĂN PHẠM VÀ NGÔN NGỮ PHI NGỮ CẢNH
CHƯƠNG 5. ÔTÔMÁT ĐẨY XUỐNG
CHƯƠNG 6. MÁY TURING
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giới thiệu
Giáo trình Kiến trúc máy tính và Hệ điều hành
4

CHƯƠNG 1. MỞ ĐẦU

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
Khái niệm văn phạm
Khái niệm Ôtômát
Giáo trình Kiến trúc máy tính và Hệ điều hành
5
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu
Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1
{a,b,c,…,z} bộ chữ gồm các ký hiệu a z
Tập các chữ cái tiếng việt
Giáo trình Kiến trúc máy tính và Hệ điều hành
6
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Xâu trên bộ chữ V là 1 dãy các ký hiệu của V
Ví dụ: 0110 là xâu trên bộ chữ {0,1}
a, ab, giathanh là xâu trên bộ chữ {a,b,…,z}
Độ dài xâu là số các ký hiệu trong xâu
Ký hiệu: độ dài xâu x là |x|
Ví dụ: |01110|=5
Giáo trình Kiến trúc máy tính và Hệ điều hành
7
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Xâu rỗng là xâu có độ dài bằng 0
Ký hiệu: , ||=0
Tập tất cả các xâu trên V là V*, {}V*
V+ =V *-{}
V*: tập vô hạn đếm được
Ví dụ: V={a,b}V*={,a,b,aa,bb,ab,ba,…}
Giáo trình Kiến trúc máy tính và Hệ điều hành
8
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Các phép toán trên xâu
Ghép tiếp: cho 2 xâu x,y. Ghép tiếp của x, y là x.y hay xy là 1 xâu viết x trước, rồi đến y sau chứ không có dấu cách.
Ví dụ: x=01
y=0110
xy=010110
Giáo trình Kiến trúc máy tính và Hệ điều hành
9
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Đảo ngược xâu x (xr): xâu được viết theo thứ tự ngược lại của xâu x
Ví dụ: x=0101 xr =1010
Chú ý: r= , 1r =1
Xâu x mà x=xr thì x là xâu hình tháp (xâu đối xứng)
Ví dụ: x=0110 xr=0110, x: xâu hình tháp
Giáo trình Kiến trúc máy tính và Hệ điều hành
10
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Lũy thừa xâu x (xn): xâu nhận được bằng cách ghép tiếp chính xâu x n lần.
xn = x.x.x...x (n lần x)
x0 =  với mọi xâu x
Ví dụ: x=01 x3 =010101
10= 
Giáo trình Kiến trúc máy tính và Hệ điều hành
11
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.2. Ngôn ngữ
Ngôn ngữ L trên bộ chữ V là tập hợp các xâu trên V, LV*
Các phép toán trên ngôn ngữ
Vì ngôn ngữ là tập hợp nên có các phép toán tập hợp: (giao), (hợp), -(hiệu), bù
Ghép tiếp 2 ngôn ngữ
Giáo trình Kiến trúc máy tính và Hệ điều hành
12
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
13
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.2. Ngôn ngữ
Ghép tiếp 2 ngôn ngữ
Cho 2 ngôn ngữ L1, L2. Ta gọi ghép tiếp L1.L2 (L1L2) của L1 và L2 là một tập hợp L1L2={xy/(xL1) và (yL2)}
x.x=x2; x.x.x=x3; x0=; xi=xi-1x
L0={}; Li=Li-1.L
L*=L0L1L2…; L+=L1L2…
Giáo trình Kiến trúc máy tính và Hệ điều hành
14
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.3. Biểu diễn ngôn ngữ
Ngôn ngữ đơn giản
Phương pháp liệt kê: ngôn ngữ có số xâu là hữu hạn và có thể xác định được.
Ví dụ: ngôn ngữ là các số tự nhiên nhỏ hơn 20 và lớn hơn 12
L={13, 14, 15, 16, 17, 18, 19}
Giáo trình Kiến trúc máy tính và Hệ điều hành
15
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.3. Biểu diễn ngôn ngữ
Ngôn ngữ đơn giản
Phương pháp sử dụng tân từ P(x): ngôn ngữ mà các xâu có cùng các đặc điểm.
Ví dụ: ngôn ngữ là các số thực nhỏ hơn 5.
L={x/ (x R) và (x<5)}
Giáo trình Kiến trúc máy tính và Hệ điều hành
16
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.3. Biểu diễn ngôn ngữ
Ngôn ngữ phức tạp
Văn phạm: cơ chế để sản sinh ra ngôn ngữ
Đối với ngôn ngữ tự nhiên: văn phạm là hệ thống ngữ pháp.
Đối với ngôn ngữ lập trình: văn phạm là qui tắc cú pháp viết chương trình.
Giáo trình Kiến trúc máy tính và Hệ điều hành
17
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.1. Định nghĩa: G=(Σ, Δ, s, p) trong đó:
Σ: tập hữu hạn các ký hiệu kết thúc.
Δ: tập hữu hạn các ký hiệu chưa kết thúc.
s: ký hiệu bắt đầu; sΔ
p: tập hữu hạn các sản xuất có dạng  với
(Σ  Δ)+, có ít nhất một ký hiệu chưa kết thúc
(ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
18
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.1. Định nghĩa: G=(Σ, Δ, s, p) trong đó:
Σ: tập hữu hạn các ký hiệu kết thúc.
Δ: tập hữu hạn các ký hiệu chưa kết thúc.
s: ký hiệu bắt đầu; sΔ
p: tập hữu hạn các sản xuất có dạng  với
(Σ  Δ)+, có ít nhất một ký hiệu chưa kết thúc
(ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
19
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
Qui ước:
Ký hiệu kết thúc được viết bằng chữ thường
Ký hiệu chưa kết thúc được viết bằng chữ in
Ký hiệu chưa kết thúc nằm bên trái của sản xuất đầu tiên là ký hiệu bắt đầu.
Giáo trình Kiến trúc máy tính và Hệ điều hành
20
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.2. Các khái niệm
Xâu (câu) và dạng câu:
 gọi là xâu khi   Σ*
 gọi là dạng câu khi (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
21
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.2. Các khái niệm
Quan hệ suy dẫn:
A có quan hệ suy dẫn ra  hay  được suy dẫn từ A, có nghĩa là từ A áp dụng các sản xuất sinh ra được 
Quan hệ suy dẫn trực tiếp: từ A áp dụng một sản xuất sinh được 
Ký hiệu: A với AΔ và (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
22
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.2. Các khái niệm
Quan hệ suy dẫn:
Quan hệ suy dẫn nhiều lần: từ A áp dụng nhiều sản xuất mới sinh được 
Ký hiệu: A +  với AΔ và (ΣΔ)*
Độ dài suy dẫn: số lần áp dụng các sản xuất
Độ dài của suy dẫn trực tiếp bằng 1
Giáo trình Kiến trúc máy tính và Hệ điều hành
23
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.3. Ngôn ngữ được sinh ra từ văn phạm
Tập hợp các câu được sinh ra từ văn phạm sẽ tạo nên ngôn ngữ.
Xác định câu được sinh ra từ văn phạm:
Từ ký hiệu bắt đầu của văn phạm áp dụng các sản xuất để sinh các câu.
Giáo trình Kiến trúc máy tính và Hệ điều hành
24
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.3. Ngôn ngữ được sinh ra từ văn phạm
Ví dụ: cho G: S0S1 | 
S==>0S1==>01
S==>0S1==>00S11==>0011
S==>0S1==>00S11==>000S111==>000111
Vậy L(G)={0n1n | với n>=0}
Giáo trình Kiến trúc máy tính và Hệ điều hành
25
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.3. Ngôn ngữ được sinh ra từ văn phạm
Ví dụ 2: Cho G: SaA
AaA | b
L(G)={anb | n>0}
Giáo trình Kiến trúc máy tính và Hệ điều hành
26
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.4. Phân cấp văn phạm của Chomsky
Nếu các sản xuất đều có dạng Aa |aB với A,B ;a : văn phạm chính quy (VP loại 3)
Nếu các sản xuất có dạng A với A; ()*: văn phạm phi ngữ cảnh (VP loại 2)
Nếu các sản xuất có dạng  với , ()*: văn phạm cảm ngữ cảnh (VP loại 1)
Nếu không có hạn chế gì trên sản xuất: văn phạm tự do (VP loại 0)
Giáo trình Kiến trúc máy tính và Hệ điều hành
27
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm
2.4. Phân cấp văn phạm của Chomsky
Lưu ý:
Văn phạm loại 3 là trường hợp đặc biệt của văn phạm loại 2.
Văn phạm loại 2 là trường hợp đặc biệt của văn phạm loại 1.
Văn phạm loại 1 là trường hợp đặc biệt của văn phạm loại 0.
Giáo trình Kiến trúc máy tính và Hệ điều hành
28
CHƯƠNG 1. MỞ ĐẦU
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Khái niệm Ôtômát
Bộ gồm: tập các trạng thái và các điều khiển dịch chuyển từ trạng thái này sang trạng thái khác khi nhận dữ liệu vào.
Ôtômát biểu diễn hoạt động của bóng điện

Ôtômát đoán nhận từ khóa int
Giáo trình Kiến trúc máy tính và Hệ điều hành
29

CHƯƠNG 2. ÔTÔMÁT HỮU HẠN

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định(DFA)
Ôtômát hữu hạn không đơn định(NFA)
Sự tương đương của DFA và NFA
Ứng dụng
Giáo trình Kiến trúc máy tính và Hệ điều hành
30
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định(Deterministic finite automata –DFA)
1.1. Mô tả
Ôtômát hữu hạn là một cái máy đoán nhận xâu gồm:
Một băng vào được chia thành nhiều ô, mỗi ô chứa một ký hiệu của xâu vào
Một đầu đọc, mỗi thời điểm trỏ vào một ô trên băng
Giáo trình Kiến trúc máy tính và Hệ điều hành
31
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
32
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.1. Mô tả
Tại một thời điểm, trạng thái q ở bộ điều khiển và ký hiệu mà đầu đọc đang đọc sẽ xác định trạng thái tiếp theo ở bộ điều khiển.
Mỗi lần đọc xong một ô, đầu đọc chuyển sang phải một ô.
Trạng thái đầu tiên ở bộ điều khiển: trạng thái bắt đầu của ôtômát
Giáo trình Kiến trúc máy tính và Hệ điều hành
33
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.2. Định nghĩa: M(Σ, Q, δ, q0, F)
Σ: bộ chữ vào
Q: tập hữu hạn các trạng thái
q0  Q: trạng thái đầu
F  Q: tập các trạng thái kết thúc
δ: hàm chuyển trạng thái có dạng δ(q,a)=p Với q,p  Q, a  Σ
Với mỗi δ(q,a)=p chỉ có một trạng thái p duy nhất
Giáo trình Kiến trúc máy tính và Hệ điều hành
34
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.2. Định nghĩa:
Ví dụ: DFA M(Σ, Q, δ, q0, F)
Σ: {0,1}
Q: {0,1}
q0: 0
F: {1} tập các trạng thái kết thúc
δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=0
Giáo trình Kiến trúc máy tính và Hệ điều hành
35
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Otomat hữu hạn đơn định
1.3. Biểu diễn các hàm chuyển trạng thái
Dùng bảng: sử dụng ma trận δ có:
Chỉ số hàng: trạng thái
Chỉ số cột: ký hiệu vào
Giá trị tại hàng q, cột a là trạng thái p, sao cho δ(q,a)=p
Giáo trình Kiến trúc máy tính và Hệ điều hành
36
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Otomat hữu hạn đơn định
1.3. Biểu diễn các hàm chuyển trạng thái
Dùng bảng:
Ví dụ: có hàm chuyển của một Otomat như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2
Giáo trình Kiến trúc máy tính và Hệ điều hành
37
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Otomat hữu hạn đơn định
1.3. Biểu diễn các hàm chuyển trạng thái
Biểu đồ dịch chuyển:
Mỗi trạng thái qQ được đặt trong các vòng tròn.
Trạng thái bắt đầu q0 có thêm dấu ‘>’ ở đầu.
Trạng thái kết thúc qF được đặt trong vòng tròn kép.
Các cung nối từ trạng thái q sang trạng thái p có mang các nhãn aΣ, có nghĩa δ(q,a)=p
Giáo trình Kiến trúc máy tính và Hệ điều hành
38
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
39
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.4. Hàm chuyển trạng thái mở rộng
Ở trạng thái q1đọc xong xâu x=a1a2a3...ai-1=yai-1 chuyển sang trạng thái qi
Có (q1,a1)=q2; (q2,a2)=q3;..., (qi-1,ai-1)=qi : ta có thể biểu diễn như sau: *(q1,x)=qi
*(q1,x)= (*(q1,y),ai-1)=qi: hàm chuyển trạng thái mở rộng.
Giáo trình Kiến trúc máy tính và Hệ điều hành
40
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.4. Hàm chuyển trạng thái mở rộng
Cho δ: δ(0,0)=0, δ(0,1)=1, δ(1,1)=1 và δ(1,0)=0 Xác định *(0,01101)=?
(0,0) = 0
*(0,01) = ((0,0),1) = 1
*(0,011) = (*(0,01),1) = 1
*(0,0110) = (*(0,011),0) = 0
*(0,01101) = (*(0,0110),1) = 1
Giáo trình Kiến trúc máy tính và Hệ điều hành
41
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.5. Hoạt động đoán nhận xâu
Từ trạng thái bắt đầu, đọc từng ký hiệu vào từ trái sang phải. Mỗi lần đọc thì xác định lại trạng thái qua hàm chuyển trạng thái.
Nếu đọc xong xâu vào mà rơi vào trạng thái kết thúc thì xâu vào được đoán nhận ngược lại xâu vào không được đoán nhận
Nếu không thể đọc xong xâu vào thì xâu vào không được đoán nhận.
Giáo trình Kiến trúc máy tính và Hệ điều hành
42
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
1.5. Hoạt động đoán nhận xâu
Xâu x được đoán nhận bởi ôtômat DFA  *(q0,x)=pF
Cho DFA M({a,b},{0,1,2,3,4},,0,{4}),
δ: δ(0,a)=1, δ(1,b)=2, δ(2,a)=3, δ(2,b)=4 δ(3,a)=3, δ(3,b)=4, δ(4,b)=4
xâu x=abaabbb có được đoán nhận k0?
Giáo trình Kiến trúc máy tính và Hệ điều hành
43
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
44
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
45
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
46
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
Trạng thái không chấp nhận được
Trạng thái không có mũi tên đi vào chỉ có mũ tên đi ra (trừ trạng thái bắt đầu).
Trạng thái chỉ có mũi tên đi vào không có mũi tên đi ra (trừ trạng thái kết thúc
Giáo trình Kiến trúc máy tính và Hệ điều hành
47
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
48
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
Bài tập:
Xây dựng DFA đoán nhận ngôn ngữ L(M) sau:
L(M)={abcnbm với n>=0, m>0}
L(M)={0(10)n với n>0}
L(M)={0n1m với n>=0, m>0}
L(M)={0n1m với n>0, m>0}
Giáo trình Kiến trúc máy tính và Hệ điều hành
49
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômát hữu hạn đơn định
Bài tập:
Xây dựng ôtômat đoán nhận L(M) là:
Một số nhị phân chẵn có độ dài xâu lớn hơn 2.
Một số nguyên có dấu, không dấu.
Một số nguyên không dấu của NNLT C
Một số thực tĩnh có dấu, không dấu.
Giáo trình Kiến trúc máy tính và Hệ điều hành
50
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định (Nondeterministic finite automata –NFA)
2.1. Định nghĩa: M(Σ, Q, δ, q0, F)
Σ: bộ chữ vào
Q: tập hữu hạn các trạng thái
q0  Q: trạng thái đầu
F  Q: tập các trạng thái kết thúc
δ: hàm chuyển trạng thái có dạng δ(q,a)=P Với qQ, a(Σ), PQ
Giáo trình Kiến trúc máy tính và Hệ điều hành
51
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định
Ví dụ: Ôtômát đoán nhận các xâu có độ dài chẵn trên bộ chữ {0,1}
Giáo trình Kiến trúc máy tính và Hệ điều hành
52
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định
Sự khác nhau giữa DFA và NFA
NFA: δ(q,a)=P, với qQ, a(Σ), PQ
DFA: δ(q,a)=p, với q,p  Q, a  Σ
NFA: có thể có dịch chuyển khi đọc 
DFA: không thể dịch chuyển khi đọc 



Giáo trình Kiến trúc máy tính và Hệ điều hành
53
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định
2.2. Hàm dịch chuyển mở rộng
(q0,a1)={q1, q2} và (q1,a2)={q3,q4} (q2,a2)={q5,q6}
*(q0,a1a2)= (q1,a2)(q2,a2)={q3,q4,q5,q6}
Có *(q,x)={p1, p2,...,pk} thì
*(q,xa)= với x*, a
Giáo trình Kiến trúc máy tính và Hệ điều hành
54
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
55
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định
2.3. Đoán nhận xâu x bởi NFA
Xâu x được đoán nhận bởi ôtômat  *(q0,x)F
Theo ví dụ trước:
*(0,01001)= {1,2}
{1,2}F ={2}  : xâu 01001 được đoán nhận
Giáo trình Kiến trúc máy tính và Hệ điều hành
56
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ôtômat hữu hạn không đơn định
2.4. Ngôn ngữ được đoán nhận bởi NFA
Cho NFA M(Σ, Q, δ, q0, F), ngôn ngữ L được đoán nhận bởi M được xác định như sau: L(M)={x*| *(q0,x)  F}
Theo ví dụ trước các xâu bắt đầu bằng 0 và kết thúc bằng 1 được đoán nhận: 00111, 0100101, 0111, 010101,...
Giáo trình Kiến trúc máy tính và Hệ điều hành
57
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Xây dựng DFA từ NFA
Cho NFA M(ΣN, QN, δN, q0, FN) thì DFA M(ΣN, QD, δD, q0, FD)
Xác định QD, δD, FD
Tạo tất cả các tập con T từ tập QN
Xác định D(T,a)=N(qi,a) với qi T, a
Mỗi tập T tương ứng với 1 trạng thái của DFA
Loại bỏ các trạng thái không chấp nhận được
Trạng thái tương ứng với tập T có chứa trạng thái kết thúc sẽ là trạng thái kết thúc của DFA
Giáo trình Kiến trúc máy tính và Hệ điều hành
58
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Xây dựng DFA từ NFA
Ví dụ:
Giáo trình Kiến trúc máy tính và Hệ điều hành
59
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Xây dựng DFA từ NFA
Ví dụ:
Giáo trình Kiến trúc máy tính và Hệ điều hành
60
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Xây dựng DFA từ NFA
Các trạng thái q1, q2, q5, q6: không chấp nhận được
q4 tương ứng {0,2}: là trạng thái kết thúc
Giáo trình Kiến trúc máy tính và Hệ điều hành
61
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ứng dụng
Đoán nhận từ khóa, số, ..., từ tố
DFA đoán nhận khóa float


NFA đoán nhận số nguyên có dấu
Giáo trình Kiến trúc máy tính và Hệ điều hành
62
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Bài tập
Vẽ NFA đoán nhận
các số nhị phân có độ dài là bội số của 4.
các từ 110, 101.
Các từ 0(101)+1
Chuyển NFA thành DFA
Các NFA ở câu (1)
Giáo trình Kiến trúc máy tính và Hệ điều hành
63
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Bài tập
NFA ở hình vẽ sau:


NFA có hàm chuyển sau:
Giáo trình Kiến trúc máy tính và Hệ điều hành
64
CHƯƠNG 2. ÔTÔMÁT HỮU HẠN
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Bài tập
NFA có hàm chuyển sau:
Giáo trình Kiến trúc máy tính và Hệ điều hành
65
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu thức chính quy
Ngôn ngữ chính quy
Văn phạm chính qui
Giáo trình Kiến trúc máy tính và Hệ điều hành
66
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.1. Định nghĩa:
Cho bộ chữ , biểu thức chính quy (BTCQ) trên  được định nghĩa đệ qui như sau:
 là BTCQ
 là BTCQ
a, a là BTCQ
Với r, s là BTCQ thì (r+s), rs, r*, s* là BTCQ
Có thể viết (r+s) hay (r  s)
Giáo trình Kiến trúc máy tính và Hệ điều hành
67
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ: Cho ={0,1} ta có:
, , 0, 1 là BTCQ
(0+1), 01, 0*, 1*, (0+1)01, (0+1)0*, (01)*, ((0+1)01)* là BTCQ
Giáo trình Kiến trúc máy tính và Hệ điều hành
68
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ:
(a+b+c) là BTCQ chỉ định 3 xâu a, b, c trên bộ chữ {a, b, c}
(a+b)* là BTCQ chỉ định mọi xâu trên {a, b}
aa*bb* hay a+b+ là BTCQ chỉ định các xâu bắt đầu bằng một số ký hiệu a, tiếp theo là một số ký hiệu b trong đó ký hiệu a và b xuất hiện ít nhất 1 lần
Giáo trình Kiến trúc máy tính và Hệ điều hành
69
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ:
(b+)(a+ab)* là BTCQ chỉ định các xâu trên {a, b} không chứa bb
(0+1)*1 là BTCQ chỉ định các xâu là số nhị phân lẻ
Giáo trình Kiến trúc máy tính và Hệ điều hành
70
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.2. Thứ tự ưu tiên của các phép toán
Phép bao đóng (*)
Phép ghép tiếp (.)
Phép hợp (+)
Ví dụ: 10*+0 : (1(0)*)+0
Giáo trình Kiến trúc máy tính và Hệ điều hành
71
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.3. Tính chất đại số
Tính giao hoán:
r + s = s + r
Tính kết hợp:
(r + s) + t = r + (s + t)
r(st)=(rs)t
Giáo trình Kiến trúc máy tính và Hệ điều hành
72
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.3. Tính chất đại số
Tính chất phân bổ
r (s + t) = rs + rt
(r + s)t = rt + st
Một số tính chất khác
(r*)* = r* r = r = r *= 
r + r = r r* = r+ + 
r+ = rr* = r*r (r*s*)* =(r + s)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
73
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.4. Ngôn ngữ được chỉ định bởi BTCQ
Ngôn ngữ L(r) được chỉ định bởi BTCQ r bất kỳ là được xây dựng dựa trên quy tắc
L( ) = {}
L(a) = {a}
L(r+s)=L(r)L(s)
L(rs) = L(r)L(s)
L(r*) = (L(r))*
Giáo trình Kiến trúc máy tính và Hệ điều hành
74
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
1.4. Ngôn ngữ được chỉ định bởi BTCQ
Ví dụ: xây dựng BTCQ chỉ định ngôn ngữ L có ít nhất một ký hiệu a và 1 ký hiệu b trên {a, b}
L(r) = L(r1)  L(r2)=L(r1+r2)
L(r1): các xâu r1 có dạng w1aw2bw3
L(r2): các xâu r2 có dạng w1bw2aw3
BTCQ chỉ định L:
(a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
75
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
Bài tập
Xây dựng BTCQ chỉ định các ngôn ngữ sau:
Tập hợp các xâu trên {a,b} có độ dài chia hết cho 3
Tập hợp các xâu trên {a, b, c} chỉ chứa 1 ký hiệu a, còn lại là các ký hiệu b và c
Tập hợp các số nhị phân có tận cùng là 11
Tập hợp các số nguyên k0 dấu chia hết cho 5
Giáo trình Kiến trúc máy tính và Hệ điều hành
76
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu Thức chính quy
Bài tập
Mô tả ngôn ngữ được chỉ định bởi BTCQ sau:
(a+b+c+d)*(a+d)
1(0+1)(0+1)(0+1)
((0+1)(0+1))+
a(a+b)*a
(ab)* + (ba)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
77
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.1. Khái niệm
Ngôn ngữ chính quy là ngôn ngữ được biểu diễn bởi biểu thức chính qui.
Ngôn ngữ chính qui được đoán nhận bởi ôtômát hữu hạn.
Ngôn ngữ được sản sinh từ văn phạm chính quy là ngôn ngữ chính qui
Giáo trình Kiến trúc máy tính và Hệ điều hành
78
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
BTCQ là a


BTCQ là 
Giáo trình Kiến trúc máy tính và Hệ điều hành
79
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
BTCQ là rs
Giáo trình Kiến trúc máy tính và Hệ điều hành
80
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
BTCQ là (r+s)
Giáo trình Kiến trúc máy tính và Hệ điều hành
81
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
BTCQ là r*
Giáo trình Kiến trúc máy tính và Hệ điều hành
82
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
Ví dụ: xây dựng NFA đoán nhận (0+1)(01)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
83
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.2. Ôtômat đoán nhận ngôn ngữ được biểu diễn bởi BTCQ
Ví dụ: (0+1)(01)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
84
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
Giáo trình Kiến trúc máy tính và Hệ điều hành
85
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
2.3. Tính chất đóng của ngôn ngữ chính quy
Cho L1(r) và L2(s) là ngôn ngữ chính quy thì:
L1(r)  L2(s): ngôn ngữ chính quy
L1(r)  L2(s): ngôn ngữ chính quy
L1(r).L2(s): ngôn ngữ chính quy
(L1(r))*: ngôn ngữ chính quy
Giáo trình Kiến trúc máy tính và Hệ điều hành
86
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
Bài tập
Vẽ NFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ sau:
(01)*(0+10*)
(10+(0+01)1*0)
(0+1)*(11+00)(0+1)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
87
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Ngôn ngữ chính quy
Bài tập
Vẽ DFA đoán nhận ngôn ngữ được biểu diễn bởi BTCQ sau:
1*01+
10*11*
(a+b)c*ab*
Giáo trình Kiến trúc máy tính và Hệ điều hành
88
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.1. Định nghĩa văn phạm tuyến tính trái
Một văn phạm G=(Σ, Δ, s, p) được gọi là văn phạm tuyến tính trái nếu tất cả các sản xuất có dạng ABw hay AB với A,BΔ; wΣ*
Ví dụ: SS a | S b | a
Giáo trình Kiến trúc máy tính và Hệ điều hành
89
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.2. Định nghĩa văn phạm tuyến tính phải
Một văn phạm G=(Σ, Δ, s, p) được gọi là văn phạm tuyến tính phải nếu tất cả các sản xuất có dạng AwB hay AB với A,BΔ; wΣ*
Ví dụ: Sa A
Aa A | b A | 
Giáo trình Kiến trúc máy tính và Hệ điều hành
90
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.3. Định nghĩa văn phạm chính quy
Văn phạm tuyến tính trái, văn phạm tuyến tính phải là văn phạm chính quy.
Giáo trình Kiến trúc máy tính và Hệ điều hành
91
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng NFA từ văn phạm tuyến tính phải
Cho văn phạm chính qui G=(ΣG , Δ, s, p) xây dựng NFA M=(Q, Σ, q0, , F) đoán nhận ngôn ngữ được sinh ra từ G
Σ = ΣG
Với AΔ thì AQ
q0 = S
Giáo trình Kiến trúc máy tính và Hệ điều hành
92
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng NFA từ văn phạm tuyến tính phải
Nếu Aa1a2...ai thì *(A,a1a2...ai)=qi : thêm qi vào Q và F
Nếu Aa1a2...ai thì đặt vào  các dịch chuyển trạng thái và thêm vào Q các trạng thái mới sao cho *(A,a1a2...ai)=qi
Giáo trình Kiến trúc máy tính và Hệ điều hành
93
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng NFA từ văn phạm tuyến tính phải
Nếu Aa1a2...aiB thì đặt vào  các dịch chuyển trạng thái và thêm vào Q các trạng thái mới sao cho *(A,a1a2...ai)=B


Nếu A thì thêm A vào F
Giáo trình Kiến trúc máy tính và Hệ điều hành
94
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng NFA từ văn phạm tuyến tính phải
Ví dụ: Sa A
Aa A | b A | 
Giáo trình Kiến trúc máy tính và Hệ điều hành
95
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng văn phạm chính quy từ NFA
Cho NFA M=(Q, Σ, q0, , F) xây dựng văn phạm chính qui G=(ΣG , Δ, s, p)
ΣG = Σ
Δ=Q
S=q0
qap nếu (q,a)=p
q nếu q  F
Giáo trình Kiến trúc máy tính và Hệ điều hành
96
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
3.4. Xây dựng văn phạm chính quy từ NFA
Ví dụ:
ΣG = {a,b}
Δ={S, A}
S=S
SaA vì (S,a)=A ; AaA vì (A,a)=A
AbA vì (A,b)=A; A vì A  F
Giáo trình Kiến trúc máy tính và Hệ điều hành
97
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
Bài tập
Vẽ otomat NFA từ G sau:
S0S| 1S | 1
S + A |- A
A0 A| 1A| ..| 9A |0|..|9
SabA
AbB| B
Bc
Giáo trình Kiến trúc máy tính và Hệ điều hành
98
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm chính quy
Bài tập
Xây dựng G từ NFA sau:
Giáo trình Kiến trúc máy tính và Hệ điều hành
99
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
100
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Xây dựng bảng đánh dấu cặp trạng thái phân biệt
Nếu p là trạng thái không kết thúc và q là trạng thái kết thúc thì {p,q} là trạng thái phân biệt.
Với a có (p,a)=ql và (q,a)=qt mà {qt, ql} là cặp trạng thái phân biệt thì {p, q} cặp trạng thái phân biệt.
Giáo trình Kiến trúc máy tính và Hệ điều hành
101
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Ví dụ: xây dựng bảng đánh dấu cặp trạng thái phân biệt cho otomat sau
Giáo trình Kiến trúc máy tính và Hệ điều hành
102
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Ta có B, D, E, G: trạng thái kết thúc
A,C,F: trạng thái không kết thúc
Áp dụng (qt1) nên các cặp sau là phân biệt:
{A,B}, {A,D}, {A,E}, {A,G},
{C,B}, {C,D}, {C,E}, {C,G},
{F,B}, {F,D}, {F,E}, {F,G}
Giáo trình Kiến trúc máy tính và Hệ điều hành
103
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Đánh dấu x vào các ô là cặp trạng thái phân biệt
Giáo trình Kiến trúc máy tính và Hệ điều hành
104
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Áp dụng (qt2) đối với từng cặp trạng thái phân biệt
{A,B}, {A,D}, {A,E}, {A,G}: vì A là trạng thái bắt đầu nên không có qt2.
{C,B}: được tạo ra từ cùng trạng thái A nên k0 có (qt2)
{C,D}: (A,1)=C và (B,1)=D nên {A,B} phân biệt (đã đánh dấu rồi)
Giáo trình Kiến trúc máy tính và Hệ điều hành
105
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
{C,E}: k0 có a thỏa (qt2)
{C,G}: (A,1)=C và (E,1)=G nên {A,E} phân biệt (đã đánh dấu rồi)
{F,B}: k0 có a thỏa (qt2)
{F,D}: (C,1)=F và (B,1)=D nên {C,B} phân biệt (đã đánh dấu rồi)
{F,E}: k0 có a thỏa (qt2)
Giáo trình Kiến trúc máy tính và Hệ điều hành
106
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
{F,G}: (E,1)=G và (C,1)=F nên {C,E} phân biệt (đã đánh dấu rồi)
(G,1)=G và (C,1)=F nên {G,C} phân biệt (đã đánh dấu rồi)
(F,1)=F và (G,1)=G nên {F,G} phân biệt (đã đánh dấu rồi)
Ta k0 tìm thêm được cặp trạng thái phân biệt nào
Giáo trình Kiến trúc máy tính và Hệ điều hành
107
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Ta được bảng đánh dấu trạng thái phân biệt sau
Giáo trình Kiến trúc máy tính và Hệ điều hành
108
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.1. Trạng thái tương đương
Ta được các cặp trạng thái tương đương sau:
{A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G}
Giáo trình Kiến trúc máy tính và Hệ điều hành
109
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.2. Hai otomat tương đương
Hai otomat cùng đoán nhận một ngôn ngữ thì tương đương.
Hai DFA tương đương thì cặp trạng thái đầu tương đương.
Cực tiểu hóa DFA: tìm DFA tương đương có số trạng thái ít nhất.
Giáo trình Kiến trúc máy tính và Hệ điều hành
110
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.3. Thuật toán
Loại bỏ các trạng thái không chấp nhận được
Xác định tất cả các cặp trạng thái tương đương
Chia các trạng thái thành các nhóm, sao cho:
các trạng thái trong cùng một nhóm tương đương nhau
Không có cặp trạng thái nào ở 2 nhóm khác nhau là tương đương.
Giáo trình Kiến trúc máy tính và Hệ điều hành
111
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.3. Thuật toán
min(S,a)=T khi qS thì (q,a)=pT
Trạng thái đầu Mmin là trạng thái có chứa trạng thái đầu của M
Trạng thái kết thúc Mmin là những trạng thái có chứa trạng thái kết thúc của M
Giáo trình Kiến trúc máy tính và Hệ điều hành
112
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
4.3. Thuật toán
Ví dụ: Cực tiểu hóa DFA ở ví dụ trước
Ta có các cặp trạng thái tương đương sau: {A,C}, {A,F}, {B,D}, {B,E}, {B,G}, {C,F}, {D,E}, {D,G}, {E,G}
Tạo thành các nhóm trạng thái tương đương: {A,C,F}, {B,D,E,G}
Giáo trình Kiến trúc máy tính và Hệ điều hành
113
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
Bài tập: Cực tiểu các DFA sau:

Giáo trình Kiến trúc máy tính và Hệ điều hành
114
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Cực tiểu hóa DFA
Bài tập: Cực tiểu các DFA sau:

Giáo trình Kiến trúc máy tính và Hệ điều hành
115
CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Sự nhập nhằng trong văn phạm phi ngữ cảnh
Ngôn ngữ phi ngữ cảnh
Dạng chuẩn của văn phạm phi ngữ cảnh
Giáo trình Kiến trúc máy tính và Hệ điều hành
116
CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Định nghĩa:
G=(Σ, Δ, s, p) trong đó:
Σ: tập hữu hạn các ký hiệu kết thúc.
Δ: tập hữu hạn các ký hiệu chưa kết thúc.
s: ký hiệu bắt đầu; sΔ
p: tập hữu hạn các sản xuất có dạng A với AΔ và (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
117
CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Ví dụ:
SS(S)S | 
Giáo trình Kiến trúc máy tính và Hệ điều hành
118
CHƯƠNG 4. VĂN PHẠM & NGÔN NGỮ PHI NGỮ CẢNH
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Suy dẫn trái, suy dẫn phải
Nếu luôn luôn thay thế ký hiệu chưa kết thúc ở bên trái nhất gọi là suy dẫn trái.
Tương tự ta có suy dẫn phải
Ví dụ: viết suy dẫn trái, suy dẫn phải tạo ra xâu a+a*a của văn phạm sau:
EE+E |E*E| (E) |a
Giáo trình Kiến trúc máy tính và Hệ điều hành
119
CHƯƠNG 4. VĂN PHẠM & NGÔN