Chứng minh của Định lý trên cũng chính là cơ sở của giải thuật chuyển một biểu thức chính quy r thành automat hữu hạn NFAε. Một điểm cần lưu ý là thứ tự ưu tiên của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng cho quá trình phân tích biểu thức chính quy thành các biểu thức con trong những trường hợp viết biểu thức chính quy ở dạng tắt (không có dấu ngoặc).
b) Giải thuật xây dựng NFA ε đoán nhận L(r).
Input: Biểu thức chính quy r
Output: NFA M = <Q, , , q0, F>; L(M) = L(r)
Process:
- Bước 1:
+ Tìm phép toán phải thực hiện cuối cùng.
+ Nếu có thì tìm các toán hạng của phép toán đó.
Ngược lại nếu không có thì đó là biểu thức không có phép toán.
- Bước 2:
+ Với mỗi toán hạng quay lại bước 1 cho đến khi toán hạng là biểu thức không có phép toán.
+ Xây dựng các automat đơn giản cho các biểu thức chính quy không chứa phép toán.
+ Xây dựng các automat cho mỗi biểu thức chính quy có chứa phép toán theo thứ tự ngược lại cho đến khi xây dựng xong automat cho biểu thức chính quy r.
Ví dụ:
Xây dựng NFAε đoán nhận ngôn ngữ được ký hiệu bởi biểu thức chính quy r = a*(a + b) b+.
+ Phân tích r
- Ta có r = r1 r2; r1= a*(a + b); r2= b+.
- r1 = r3 r4; r3 = a*; r4 = (a + b).
- r3 = (r5 )* ; r5= a.
- r4 = r6 + r7 ; r6 = a; r7 = b.
- r2 = (r8) + ; r8 = b.
+ Xây dựng r
Start
0
b
1
Start
2
b
3
Start
4
a
5
Start
6
a
7
- r = b
8
- r = b
7
- r = a
6
- r = a
5
a
Start
ε
4
5
ε
8 9
ε
2
b
3
ε
- r = r + r
4 6 7
- r = (r )*
3 5
Start
10
6
a
7
11
ε
ε
- r = (r ) +
2 8 ε
Start
12
0
b
1
13
- r = r r
1 3 4
Start
10
6
ε
a
7
ε
4
a
5
ε
8
9
ε
ε
2
b
3
ε
ε
- r = r r
ε
4
5
ε
Start
10
6
a
7
8
ε
9
ε
2
b
3
ε
12
0
b
1
13
1 2 a
Hình 2.24. NFAε biểu diễn cho r = a*(a + b) b+
Như vậy, biết biểu thức chính quy r ta xây dựng được automat hữu hạn NFAε đoán nhận ngôn ngữ L(r). Vấn đề đặt ra là biết automat hữu hạn M bằng phương pháp nào có thể đưa ra được biểu thức chính quy biểu diễn cho ngôn ngữ được đoán nhận bởi M.
2) Xây dựng biểu thức chính quy r biểu diễn L(M)
a) Định lý
Nếu L được đoán nhận bởi một DFA, thì L được ký hiệu bởi một biểu thức chính quy.
Chứng minh:
Đặt L là tập hợp được đoán nhận bởi DFA M = <{q , q ,..., q }, Σ, δ, q , F>.
1 2 n 1
k
Đặt R
là tập hợp tất cả các xâu x sao cho δ(q , x) = q và nếu δ(q , y) = q , với y là
ij i j i l
k
tiền tố bất kỳ của x, khác x hoặc ε, thì l ≤ k. Tức là R
là tập hợp tất cả các xâu làm
ij
cho automat đi từ trạng thái qi tới qj không đi ngang qua trạng thái nào (được đánh số) lớn hơn k. (Chú ý, khái niệm “đi ngang qua một trạng thái” có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). Vì chỉ có n
n
trạng thái nên R
ij
k
Ta định nghĩa R
ij
sẽ là tập hợp tất cả các xâu làm automat đi từ qi tới qj.
một cách đệ quy như sau:
k
R = R
ij
k-1
ik
k-1
(R
kk
k-1
)* R
kj
k-1
R
ij
(1)
0 { a | δ(q , a) = q } nếu i ≠ j
R = i j
ij
{ a | δ(q , a) = q } {ε} nếu i = j
i j
k
Một cách hình thức, R
ij
định nghĩa như trên là các xâu vào hay nguyên nhân
đưa M từ q tới q không đi ngang qua trạng thái cao hơn q , nghĩa là xảy ra một
i j k
trong hai trường hợp sau:
k-1
1. Nằm trong R
như q ).
k
(để không bao giờ đi ngang qua một trạng thái nào cao
ij
2. Bao gồm một xâu trong Rk-1ik (xâu làm M chuyển đến qk), theo sau bởi không hoặc nhiều xâu trong Rk-1ik (xâu làm M chuyển từ qk trở về qk mà không
k-1
ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là một xâu trong R
kj
(xâu làm M chuyển từ q đến q ).
k j
k
Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy r
k
ký hiệu cho
ij
ngôn ngữ R
. Ta quy nạp theo k như sau:
ij
0 0
- k = 0: khi đó R
là tập hợp hữu hạn các xâu có một ký hiệu hoặc ε. Vậy r
ij ij
có thể viết dưới dạng a + a + ... + a (hoặc a + a + ... + a + ε nếu i = j). Trong đó
1 2 p 1 2 p
{a , a ,..., a } là tập hợp tất cả các ký hiệu a sao cho δ(q , a) = q . Nếu không có ký
1 2 p i j
∅
0
hiệu a nào như thế thì (hoặc ε khi i = j) ký hiệu cho r .
ij
k
- Công thức (1) cho R
chỉ liên quan đến các phép toán trên biểu thức chính
ij
quy: hợp, nhân ghép và bao đóng. Hơn nữa theo giả thiết quy nạp, với mỗi l, k và
m tồn tại biểu thức chính quy r
k-1
sao cho L(r
k-1
) = R
k-1
k
. Vậy đối với r
ta có
thể chọn biểu thức chính quy:
k-1
(r
lm
k-1
) (r
k-1
)* (r
lm lm ij
k-1
) + r
ik kk kj ij
n n
Cuối cùng ta có nhận xét rằng L(M) =
các nhãn của tất cả các đường đi từ q tới q .
1 j
R
qj F
vì R
1j
ký hiệu cho tất cả
1j
Vậy L(M) được ký hiệu bởi biểu thức chính quy r = r trong đó tập F = {q , q ,..., q }.
j1 j2 jp
Ví dụ:
n
1j1
n
+ r
1j2
+ ... + r
n
,
1jp
Viết biểu thức chính quy ký hiệu cho ngôn ngữ được đoán nhận bởi DFA hình sau:
0
0
Start
q1
0
q2
1
q3
1
1
Hình 2.25. DFA
Gọi DFA được chỉ ra trong hình 2.16 là M = <Q, , δ, q0, F> trong đó:
- Q = {q , q , q };
1 2 3
- = {0, 1};
- δ:
δ(q , 0) = {q };
1 2
δ(q , 1) = {q };
1 3
δ(q , 0) = {q };
2 1
δ(q , 1) = {q };
2 3
δ(q , 0) = {q };
3 2
δ(q , 1) = {q };
3 2
- q0 = q ;
1
- F = {q , q }.
2 3
Ta thấy, tập hợp tất cả các xâu được đoán nhận bởi DFA trên là các xâu làm cho automat chuyển từ trạng thái bắt đầu q đến một trong hai trạng thái kết thúc q
1 2
và q và không chuyển qua số tối đa là 3 (k = 3) trạng thái của automat. Vậy ta cần
3
viết biểu thức chính quy ký hiệu cho tập hợp này như sau:
3 3
r = r + r
12 13
Theo công thức đã được chứng minh trong định lý trên, ta có thể tính được
k
các giá trị r
với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ
ij
ra trong bảng sau:
k = 0 | k = 1 | k = 2 | |
k r 11 | ε | ε | (00)* |
k r 12 | 0 | 0 | 0(00)* |
k r 13 | 1 | 1 | 0*1 |
k r 21 | 0 | 0 | 0(00)* |
k r 22 | ε | ε + 00 | (00)* |
k r 23 | 1 | 1 + 01 | 0*1 |
k r 31 | ∅ | ∅ | (0 + 1)(00)*0 |
k r 32 | 0 + 1 | 0 + 1 | (0 + 1)(00)* |
k r 33 | ε | ε | ε + (0 + 1)0*1 |
Có thể bạn quan tâm!
-
Automat Hữn Hạn Đơn Định Đoán Nhận Ngôn Ngữ L -
Sự Tương Đương Giữa Nfa Có Và Không Có Ε-Dịch Chuyển -
Một Số Tính Chất Đại Số Của Biểu Thức Chính Quy -
Biểu Diễn Automat Bằng Đồ Thị -
Đường Đi Trong Đồ Thị Chuyển Của Dfa M -
Ngôn ngữ hình thức - 13
Xem toàn bộ 254 trang tài liệu này.
Bảng 2.14. Mô tả quá trình tính r
Bằng cách dùng các công thức tương đương như
(r + s) t = rt + st và (ε + r)* = r* để đơn giản các biểu thức, chẳng hạn khi tính biểu thức:
1 0 0
r = r (r
22 21 11
0
)* r
12
0
+ r = 0(ε)*0 + ε = 00 + ε
22
Tương tự, khi đơn giản biểu thức
2 1
r = r
13 12
1 1
(r )* r
22 23
1
+ r = 0(00 + ε)*(1 + 01) + 1
13
Ta nhận thấy (00 + ε)* tương đương với (00)* và (1 + 01) thì tương đương với (ε + 0)1 nên ta rút gọn:
2
r = 0(00)*(ε + 0)1 + 1
13
Mặt khác, chú ý rằng (00)*(ε + 0) thì tương đương với 0*, vì thế 0(00)*(ε + 0)1 + 1
cũng bằng 00*1 + 1 hay cuối cùng là 0*1.
3
Để hoàn thành việc xây dựng biểu thức chính quy cho M, ta cần tính r và
12
3
r . Ta viết:
13
3 2
r = r
12 13
2 2 2
(r )* r + r
33 32 12
= 0*1(ε + (0 + 1)0*1)*(0 + 1)(00)* + 0(00)*
= 0*1((0 + 1)0*1)*(0 + 1)(00)* + 0(00)*
3
và r
13
2 2
= r (r
13 33
2 2
)* r + r
33 13
= 0*1(ε + (0 + 1)0*1)*(ε + (0 + 1))0*1) + 0*1
= 0*1((0 + 1)0*1)*
Vậy biểu thức chính quy có dạng:
3 3
r = r + r
12 13
= 0*1((0 + 1)0*1)*(ε + (0 + 1)(00)*) + 0(00)*
Như vậy, về nguyên tắc, biết automat hữu hạn ta có thể xây dựng được biểu thức chính quy biểu diễn cho ngôn ngữ được đoán nhận bởi automat hữu hạn. Vì từ NFA ta chuyển về được NFA đoán nhận cùng một ngôn ngữ; từ NFA ta chuyển về được DFA đoán nhận cùng một ngôn ngữ và từ DFA theo định lý trên ta tìm được biểu thức chính quy biểu diễn cho ngôn ngữ được đoán nhận bởi DFA.
2.3. Văn phạm chính quy
Phần này sẽ chứng tỏ sự tương đương của hai quan điểm, quan điểm sinh và quan điểm đoán nhận ngôn ngữ. Nói cách khác ta sẽ chứng tỏ ngôn ngữ sinh bởi văn phạm chính quy trùng với ngôn ngữ được đoán nhận được bởi Automat hữu hạn.
2.3.1. Văn phạm tuyến tính
1) Định nghĩa
- Văn phạm G = (N, T, P, S) được gọi là tuyến tính trái (left – linear) nếu mọi luật sinh của nó có dạng A → Bw hoặc A → w; trong đó: A, B N và w T*.
- Văn phạm G = (N, T, P, S) được gọi là tuyến tính phải (right – linear) nếu mọi luật sinh của nó có dạng A → wB hoặc A → w; trong đó: A, B N và w T * .
- Văn phạm G = (N, T, P, S) được gọi là văn phạm chính quy nếu nó là văn phạm tuyến tính trái hoặc văn phạm tuyến tính phải.
2) Ví dụ
a) Các văn phạm sau đây là văn phạm chính quy:
- Văn phạm G1 = ({S}, {a, b}, P1, S) với các luật sinh được cho như sau: S → abS a là văn phạm tuyến tính phải.
- Văn phạm G2 ({S, A, B}, {a, b}, P2, S) với các luật sinh được cho như sau: S → Aab; A → AabB; B → a là văn phạm tuyến tính trái.
- Văn phạm G1 = (N1, T1, P1, S1), trong đó:
N1 = {S}; T1 = {a, b}; S1 = S; P1với các luật sinh được cho như sau: S → bS| a.
G1 là văn phạm tuyến tính phải.
Ngôn ngữ sinh bởi văn phạm G1 là r = b*a.
- Văn phạm G2 = (N2, T2, P2, S2), trong đó:
N2 = {S, A, B}; T2= {a, b}; S2 = S; P2 với các luật sinh: S → Sb | a; A → Aa| Bb| b | ; B → a | b.
G2 là văn phạm tuyến tính tính trái.
Ngôn ngữ sinh bởi văn phạm G1 là r = ab*.
b) Ngôn ngữ được biểu diễn bởi biểu thức chính quy 01* được sinh bởi văn phạm tuyến tính phải có các luật sinh: S → 0A; A → 1A|ε (1)
Và bởi văn phạm tuyến tính trái có các luật sinh: S → S1| 0 (2)
2.3.2. Sự tương đương giữa văn phạm chính quy và automat hữu hạn
1) Định lý 1
Nếu G = (N, T, P, S) là văn phạm chính quy thì tồn tại Automat hữu hạn M sao cho L(M) = L(G).
Chứng minh:
Trước hết, ta giả sử văn phạm tuyến tính phải G = (N, T, P, S) sinh ra ngôn ngữ chính quy L(G). Ta xây dựng một NFA có chứa ε-dịch chuyển M (Q, T, δ, [S], [ε]) mô phỏng các dẫn xuất trong G (đoán nhận L(M) = L(G)).
Q bao gồm các trạng thái có dạng [α] với α là S hoặc chuỗi hậu tố của vế phải một luật sinh nào đó trong P.
Ta định nghĩa δ như sau :
1) Nếu A là một biến, thì δ([A], ε) = {[α] | A → α là một luật sinh}