Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 2: Ngôn ngữ, văn phạm và ôtômát - Nguyễn Thị Thùy Linh
Nội dung
Ba khái niệm cơ bản
Chương 2
1. Ngôn ngữ (languages)
Khái niệm ngôn ngữ
Biểu diễn ngôn ngữ
Hệ viết lại và vấn đề biểu diễn ngôn ngữ.
Ngôn ngữ, văn phạm và
2. Văn phạm (grammar)
Định nghĩa văn phạm
ôtômát
Sự phân cấp văn phạm
2
3. Ôtômat (automata)
Tổng quan về ngôn ngữ:
Ký hiệu, bộ chữ cái, chuỗi
•
•
Ký hiệu (symbol):
Ngôn ngữ tự nhiên:tiếng Việt,tiếng Anh, …
Ngôn ngữ lập trình: Pascal, C/C++, …
ĐN ngôn ngữ trong các từ điển:
. Ví dụ: các chữ cái a,b,c,…; các chữ số 1,2,3,…
Bộ chữ cái (alphabet hay bảng chữ cái) Σ :là một tập hợp không rỗng
các ký hiệu
Là tập hợp các câu theo cấu trúc quy định nào đó
. Bảng chữ cái La Mã : {I, V, X, L, C, D, M}
. Bảng chữ số nhị phân: {0, 1}
Biểu thị các ý nghĩ, các sự kiện hay các khái niệm
Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng
. Bảng chữ số thập phân: {0,1,2,…,9}
. Bảng chữ cái Latinh :{A, B, C, ... , Z, a, b, c, ... , z}
. Bảng chữ cái Hi Lạp: {, β, γ, …,}
Qui ước:
Định nghĩa trên chưa đủ chính xác để nghiên cứu về ngôn
ngữ hình thức (ngôn ngữ dùng chung cho cả ngôn ngữ tự
nhiên lẫn ngôn ngữ lập trình). Chúng ta cần xây dựng một
định nghĩa toán học cho khái niệm về ngôn ngữ.
.
. Bộ chữ cái thường dùng Σ = {a,b,c} , Σ = {0,1}
. Các kí hiệu u,v,w,x,y,z,t dùng gọi cho tên chuỗi.
3
4
1
Ký hiệu, bộ chữ cái, chuỗi
Ký hiệu, bộ chữ cái, chuỗi
Chuỗi (Xâu, string) là một dãy hữu hạn các ký hiệu xếp liên tục
nhau gồm:
Chuỗi tiền tố: là một chuỗi con bất kỳ nằm ở đầu chuỗi đó.
Chuỗi hậu tố:là một chuỗi con bất kỳ nằm ở cuối chuỗi đó.
Các ký hiệu thuộc Σ
Ví dụ: chuỗi abc có các tiền tố là , a, ab, abc và có các hậu tố
là , c, bc, abc.
Mỗi ký hiệu có thể xuất hiện nhiều lần
Ví dụ: 010001 là một chuỗi trên bộ chữ cái Σ = {0, 1}
w = abbcab là một chuỗi trên bộ chữ cái Σ = {a,b,c}
Chuỗi nối kết (ghép): ký hiệu bởi vw, là một chuỗi được tạo
bằng cách viết v rồi viết w tiếp theo sau, không có khoảng cách.
Độ dài chuỗi w, ký hiệu bởi |w|, là số những ký hiệu hợp thành w.
Chẳng hạn |010001| = 6.
Ví dụ: ghép Long và Int là LongInt.
Nối kết với chuỗi rỗng: εw = wε = w (w)
khi đó ε là đơn vị của phép nối kết
|uv| = |u| + |v|
Chuỗi rỗng, ký hiệu (hay ), là chuỗi có độ dài 0, tức là chuỗi
không có ký hiệu nào.
Chuỗi con: Chuỗi v được gọi là chuỗi con của chuỗi w nếu v được
tạo bởi một dãy các ký hiệu kề nhau trong w.
|εw| = |wε| = |w|
5
6
Chẳng hạn ab, abb, bc, cb là các chuỗi con của chuỗi abbcb.
Ký hiệu, bộ chữ cái, chuỗi
Khái niệm về bao đóng sao và bao đóng dương
Đảo ngược của một chuỗi u, ký hiệu uR : là chuỗi u viết theo
thứ tự ngược lại, nghĩa là nếu:
* và +: (bao đóng sao và bao đóng dương)
u = a1a2…an thì uR = anan-1…a1.
●
* : tập hợp tất cả các chuỗi con được sinh ra từ bộ chữ cái ,
Đương nhiên R = .
kể cả chuỗi rỗng ε.
Phép lũy thừa: Cho w là một chuỗi
●
+ : tập hợp tất cả các chuỗi con, được sinh ra từ bộ chữ cái ,
ngoại trừ chuỗi rỗng ε.
w0 =
* = + + {ε}
+ = * - {ε}
w1 = w
w2 = ww
w3 = ww2
wn = wwn-1
●
= {0,1} thì:
* = {ε, 0, 1, 00, 01, 10, 11, 000, …}
+ = {0, 1, 00, 01, 10, 11, 000, …}
Chuỗi 010210 * vì có số 2
Rõ ràng Σ thì hữu hạn còn Σ* và Σ+ thì vô hạn đếm được
7
8
2
Các phép toán trên ngôn ngữ
Ngôn ngữ (Languages)
Từ các ngôn ngữ có trước, ta có thể thu được các ngôn ngữ mới nhờ áp
dụng các phép toán lên ngôn ngữ. Các phép toán trên tập hợp đều có thể
áp dụng lên các ngôn ngữ.
•
Một ngôn ngữ (hình thức) L là một tập con của Σ* hay nói cách khác
là một tập hợp các chuỗi của các ký hiệu được sinh ra từ bộ chữ cái
Σ.
Phép phần bù (complement):
•
Ví dụ: Cho Σ = {a, b}
= * - L
Σ* = {, a, b, aa, ab, ba, bb, aaa, aab, … }
Ta có:
Phép nối kết (concatenation):
L
•
•
•
•
•
•
•
L1L2 = {w1w2 | w1 L1 và w2 L2} trên bộ chữ cái Σ1 Σ2
L = là ngôn ngữ trên bộ chữ cái Σ tùy ý
L = {} là ngôn ngữ trên bộ chữ cái Σ tùy ý
L = {a, aa, aab} là một ngôn ngữ hữu hạn trên Σ = {a,b}
L = {(ab)n | n 0 } là một ngôn ngữ vô hạn trên Σ ={a,b}
L = {an bn | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {a,b}
L = {0n 1n | n ≥ 0 } là một ngôn ngữ vô hạn trên Σ = {0,1}
L0 = {ε}
L1 = L
L2 = LL
L3=LL2
Ln = L Ln-1
9
10
Các phép toán trên ngôn ngữ
Ví dụ: cho L = {a, ba} trên bộ chữ cái = {a,ba}
• L2 = {aa, aba, baa, baba}
Phép bao đóng (closure): Thành lập một ngôn ngữ bằng cách kết nối
các chuỗi (với số lượng bất kỳ) các chuỗi của một ngôn ngữ L cho
trước:
• L3 = {aaa, aaba, abaa, ababa, baaa,baaba, babaa,
Bao đóng sao của một ngôn ngữ L, ký hiệu L*
L* = L0 L1 L2 …
bababa}
Trong đó Li cho bởi định nghĩa đệ quy sau:
• L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, …}
• L+ = { a, ba, aa, aba, baa, baba, aaa, aaba, …}
L0 = {}
Li = LLi-1 với i 1.
Đô
̣ ưu tiên cꢀa phꢁp toꢂn : (1)bao đóng, (2)ghꢀp,
∞
Bao đóng Kleene:
L* = 푖=0 퐿푖
(3)hợp
∞
Bao đóng dương (positive): L+
Chú ý: L* = L0 + L+
=
푖=1 퐿푖 = L1 L2 L3 … Ln
11
12
3
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Biểu diễn ngôn ngữ
Ta thường biểu diễn ngôn ngữ bằng một văn phạm hay một Ôtômát. Văn
phạm hay Ôtômát gọi là hệ viết lại (written rule).
Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ ={a, b}, L định nghĩa như sau:
(1) L
1. Cách 1: Liệt kê chuỗi: L = {aa, aba, baa, baba}
2. Cách 2: Mô tả đặc điểm chꢀ yếu: L = {ai | i là số nguyên tố}
3. Cách 3: Biểu diễn thông qua văn phạm và automata:
(2) Nếu X L, thì aXb L.
(3) Không còn chuỗi nào khác thuộc L
•
•
Cho phép biểu diễn ngôn ngữ một cách tổng quát
Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ
Ban đầu, do (1), ta có chuỗi L. Xem là X thì do (2) ta sẽ có chuỗi ab L
tức là chuỗi ab L. Bây giờ xem ab như là X thì do (2) ta sẽ có aabb L.
Tương tự ta có aaabbb L, …cứ thế tiếp tục ta có các chuỗi aibi L (i≥0).
VD văn phạm có tập qui tắc: P={Câu đơn Chủ ngữ Vị ngữ;
….} là cơ chế sản sinh ra mọi câu đơn của Tiếng Việt.
Trên đây cho ta một quy tắc viết lại chuỗi.
•
Automata: cơ chế cho phép đoán nhận một chuỗi bất kỳ có
thuộc một ngôn ngữ L hay không?
Dễ nhận thấy rằng ngôn ngữ cần tìm là L = {aibi| i = 0, 1, 2, …}
13
14
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Ví dụ 2: Ngôn ngữ L được định nghĩa là tập tất cả các chuỗi
có thể thu về chuỗi rỗng bằng một dãy phép thay thế các
chuỗi con ab bởi . Định nghĩa này cho ta một cách đoán
nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không.
Định nghĩa: Một hệ viết lại là một bộ đôi W = (Σ, P) trong
đó Σ là bộ chữ cái và P là tập hợp hữu hạn các cặp chuỗi
trên Σ. Một phần tử (Σ, w) của P được gọi là một quy tắc
viết lại hay một sản xuất và thường viết Σ w.
Đoán nhận cũng là một quy tắc viết lại chuỗi. Chẳng hạn sau
đây là một quá trình đoán nhận trong đó chuỗi con ab thay
thế được gạch dưới.
ĐN suy dẫn trực tiếp: Ta nói chuỗi x trên Σ suy dẫn trực
tiếp chuỗi y, và viết x Wy hoặc viết gọn x y khi hệ W
đã rõ, khi và chỉ khi tồn tại các chuỗi x1, Σ, x2 và w sao cho
x = x1 Σ x2, y = x1wx2, và Σ w là một sản xuất trong P.
aabbab
abab
ab
Như thế chuỗi aabbab là thuộc ngôn ngữ L
15
16
4
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
ĐN suy dẫn gián tiếp: Ta nói chuỗi x suy dẫn chuỗi
Qui tắc viết gộp: Nếu trong P, ta có một loạt
các sản xuất có cùng một vế trái dạng
y, và viết x * y,
w
Σ w1
Σ w2
…
hoặc viết gọn là x *y khi hệ W đã rõ, khi và chỉ khi
tồn tại một dãy các chuỗi trên Σ dạng x0, x1, …, xk
với k 0 sao cho x0 = x, xk = y, và xi suy dẫn trực
tiếp xi+1 đối với 0 i k-1 .
Σ wn
thì các sản xuất đó thường được viết gộp vế trái là:
Σ w1| w2| …| wn
17
18
Hệ viết lại và vấn đề biểu diễn ngôn ngữ (tt)
Văn phạm là gì?
Các từ điển định nghĩa văn phạm một cách không chính xác
là một tập các qui tắc về cấu tạo từ và các qui tắc về cách
liên kết các từ lại thành câu.
Các ngôn ngữ cho ở các ví dụ 1 và ví dụ 2 ở trên có
thể biểu diễn bởi hệ viết lại như sau:
Ví dụ:
Ngôn ngữ
Hệ viết lại
Cho đoạn văn phạm tiếng Anh sau
Ví dụ 1: Cho L là một ngôn ngữ trên bộ chữ {a, b}, định
nghĩa như sau:
Ls(W, {X}) {a, b}*,
trong đó:
<sentence>
<noun phrase>
<predicate>
<article>
→
→
→
→
→
→
<noun phrase><predicate>,
<article><noun>,
<verb>,
L
W = ({a, b, X}, {X ,
X aXb}).
Nếu X L, thì aXb L.
Vậy L = {ai bi | i ≥ 0}
a | the,
Ví dụ 2: Ngôn ngữ L được định nghĩa là tập tất cả các Lđ = (W, {}),
chuỗi có thể thu về chuỗi rỗng bằng một dãy phép thay
thế các chuỗi con ab bởi . Định nghĩa này cho ta một
cách đoán nhận một chuỗi có thuộc ngôn ngữ hay không?
<noun>
boy | dog,
trong đó:
W = ({a, b}, {ab }).
<verb>
runs | walks,
Trường hợp này L không thể biểu diễn!
19
20
5
Định nghĩa văn phạm
Các luật sinh (production) đôi khi còn được gọi là các qui tắc
(rule) hay luật viết lại (written rule)
Định nghĩa 1: văn phạm cấu trúc G là một hệ thống gồm
4 thành phần G(V, T, P, S)
Ví dụ 3: Cho văn phạm sau
G = (V={S, A, B}, T={a, b}, P,S), với P:
S → aAS | bBS | λ,
• V (variables): tập các biến (VD: A, B, C, …)
• T (terminal): tập các ký hiệu kết thúc (V T = Ø) (VD:
a, b, c, …, w, x, y, ...)
A → aaA | b,
B → bbB | a,
• P (production): tập luật sinh, dạng α→β với α, β (V
T)*
Văn phạm là cơ chế sinh ra mọi chuỗi con của ngôn ngữ:
Thật vậy, mọi dẫn xuất bắt đầu từ S có dạng:
• S (start): ký hiệu bắt đầu (S V)
S →* ab
S →* ba
…
21
22
Định nghĩa ngôn ngữ L sinh bởi văn phạm G
Một số qui ước
Các kí tự chữ hoa A, B, C, D, E và S biểu thị các biến; S là kí
hiệu khởi đầu trừ Khi được phát biểu khác đi.
Định nghĩa 2: Ngôn ngữ L được sinh bởi văn phạm G:
L (G) = {w w T * và S * w}
Các kí tự chữ thường a, b, c, d, e, các kí số, các chuỗi in đậm
biểu thị các kí hiệu kết thúc (terminal).
Các kí tự chữ hoa X, Y, Z biểu thị các kí hiệu có thể hiểu là kí
hiệu kết thúc hoặc biến.
Ví dụ:Tìm ngôn ngữ được sinh ra bởi văn phạm trong ví dụ 3
trên.
Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các kí hiệu
kết thúc.
Văn phạm tương đương: là 2 văn phạm sinh ra cùng một
ngôn ngữ (G1 tương đương G2 L(G1)=L(G2) )
Các kí tự chữ thường Hi Lạp ,β,γ biểu thị chuỗi các biến và
các kí hiệu kết thúc.
23
24
6
Ví dụ: Hai văn phạm tương đương
Dẫn xuất câu (derivation)
G1(V,T,P,S)
G2(V,T,P,S)
Nếu w ∈ L(G) thì phải tồn tại dãy dẫn xuất (quá
V = {A,B,C}
T = {a,b}
P = {A BC
B aB | a
C bC | b }
S = A là kí hiệu bắt đầu
V = {S,A,B}
T = {0,1}
P = {S 0A
A 0A | 1B |1
B 1B | 1 }
S là kí hiệu bắt đầu
trình dẫn xuất):
S w1 w2 w3 … wn w
Hệ viết lại là S * w
Tìm ngôn ngữ được sinh ra bởi văn phạm?
Có nhận xét gì về G1 và G2?
Dãy này được gọi là một sự dẫn xuất câu của w
Dạng câu (sentential forms)
Hướng dẫn:
L1= {anbm | n,m 1} trên ={a,b} L2 = {0n1m | n,m > 0} trên
={0,1}
Nhận xét : Rõ ràng L1= L2 nên G1 G2
SV tự chứng minh!
Dãy S,w1,w2,…wn được gọi là các dạng câu của sự
dẫn xuất.
Mở rộng: Cho G1 tìm G2 sao cho G2 G1.
G2 tìm được không nhất thiết phải giống như trên
Câu w cũng được xem là một dạng câu đặc biệt
25
26
Phân cấp văn phạm
Bằng cách áp đặt một số quy tắc hạn chế trên các luật sinh,
Noam Chomsky đề nghị một hệ thống phân loại các văn
phạm dựa vào tính chất của các luật sinh.
Ví dụ: cho văn phạm
G = ({S},{a,b},P,S} với dẫn xuất P sau:
P = { S aSb | λ }
Một dẫn xuất từ S có dạng:
S aSb aaSbb aabb
Gọi là một dãy dẫn xuất (quá trình dẫn xuất câu)
Vì vậy có thể viết S * aabb
Chuỗi aabb là một câu của ngôn ngữ được sinh ra
bởi G, còn aaSbb là một dạng câu
Ngôn ngữ tương ứng với văn phạm này là:
L(G) = {anbn | n ≥ 0 }
27
28
7
Phân cấp văn phạm
Phân cấp văn phạm
Loại 0 – Văn phạm không hạn chế
(Unrestricted Grammar): không cần thỏa điều
kiện ràng buộc nào trên tập các luật sinh
Loại 3 – Văn phạm chính quy (RG – Regular Grammar): có mọi luật sinh dạng
tuyến tính phải hoặc tuyến tính trái.
•
•
VPCQ Tuyến tính phải (gọi tắt VPCQ phải):
A → wB | w
Loại 1 – Văn phạm cảm ngữ cảnh (CSG –
Context Sensitive Grammar): nếu văn phạm G
có các luật sinh dạng →β và |β| ≥ ||
VPCQ Tuyến tính trái (gọi tắt VPCQ trái):
A → Bw | w
Loại 2 – Văn phạm phi ngữ cảnh (CFG –
Context-Free Grammar): có luật sinh dạng A→
với A là một biến đơn và là chuỗi các ký hiệu
thuộc (V T)*
Với A, B là các biến đơn, w là chuỗi ký hiệu kết thúc (có thể là rỗng)
Nếu ký hiệu L0, L1, L2, L3 là các ngôn ngữ được sinh ra bởi văn phạm loại 0, 1, 2,
3, ta có:
L3 L2 L1 L0
29
30
Các ví dụ về văn phạm
Các ví dụ về văn phạm
Ví dụ 2: văn phạm G( {S}, {a, b}, P, S )
Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S )
P =
S aS
S aA
A bA
A b
P =
S aSb
S ab
1. G là văn phạm gì?
1. G là văn phạm gì?
2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ
2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ
tìm được là ngôn ngữ gì?
tìm được là ngôn ngữ gì?
31
32
8
Gợi ý đáp án
Các ví dụ về văn phạm
Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S )
Ví dụ 1: văn phạm G( {S, A}, {a, b}, P, S )
S aS
S aA
A bA
S → aSBC
S → aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc
P =
P =
A b
Đây là văn phạm chính qui (dạng tuyến tính phải)
Một dẫn xuất từ S có dạng:
1. G là văn phạm gì?
S aS aaS aaaA aaabA aaabbA aaabbbA
aaabbbb = a3 b4
2. Tìm ngôn ngữ L(G) được sinh bởi văn phạm. Ngôn ngữ
tìm được là ngôn ngữ gì?
L(G) = {anbm | n,m ≥ 1}
33
34
Gợi ý đáp án
Gợi ý đáp án
Ví dụ 3: văn phạm G( {S, B, C}, {a, b, c}, P, S )
Ví dụ 2: văn phạm G( {S}, {a, b}, P, S )
S → aSBC
S → aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc
S aSb
P =
S ab
P =
Đây là văn phạm phi ngữ cảnh
Một dẫn xuất từ S có dạng:
Đây là văn phạm cảm ngữ cảnh
S aSb aaSbb aaaSbbb aaaabbbb = a4b4
L(G) = {anbn | n ≥ 1}
Một dẫn xuất từ S: S aSBC aaBCBC aabCBC
aabBCC aabbCC aabbcC aabbcc=a2b2c2
L(G) = {anbncn | n ≥ 1}
35
36
9
Định nghĩa Ôtômát (Automata)
Ôtômát (Automata)
Định nghĩa: là máy trừu tượng, là thiết bị có thể tự động
thực hiện công việc mà không cần sự can thiệp của
con người.
Nội dung:
1. Định nghĩa Ôtômát
2. Cấu tạo
• Cơ cấu và hoạt động đơn giản nhưng có khả năng
đoán nhận ngôn ngữ
3. Hoạt động
4. Phân loại
• Con người dựa trên tập quy tắc lập trình sẵn cho máy
một ‘lộ trình’ để thực hiện
• Máy trừu tượng này là mô hình điển hình của máy tính
số ngày nay
5. Ứng dụng
37
38
Cấu tạo Ôtômát
Chức năng cꢂc bộ phận
Thiết bị đầu vào (input file): là nơi mà các chuỗi nhập (input string) được
ghi lên, và được ôtômát đọc nhưng không thay đổi được nội dung của nó.
Nó được chia thành các ô (cells, squares), mỗi ô giữ được một kí hiệu.
Máy này gồm các thành phần chủ yếu như sau:
Cơ cấu nhập (input mechanism): là bộ phận có thể đọc input file từ trái
sang phải, một kí tự tại một thời điểm. Nó cũng có thể dò tìm được điểm kết
thúc của chuỗi nhập (eof, #).
INPUT
Bộ nhớ tạm (temporary storage): là thiết bị bao gồm một số không giới
hạn các ô nhớ (cell), mỗi ô có thể giữ một kí hiệu từ một bảng chữ cái
(không nhất thiết giống với bảng chữ cái ngõ nhập). Ôtômát có thể đọc và
thay đổi được nội dung của các ô nhớ lưu trữ (storage cell).
Đơn vị điều khiển (control unit): mỗi ôtômát có một đơn vị điều khiển, cái
mà có thể ở trong một trạng thái bất kỳ trong một số hữu hạn các trạng
thái nội, và có thể chuyển đổi trạng thái trong một kiểu được định nghĩa
sẵn nào đó.
Bộ điều khiển
OUTPUT
BỘ NHỚ
39
40
10
Hoạt động Ôtômát
Các khái niệm
Trạng thái nội (internal state): là một trạng thái của đơn vị điều khiển
mà nó có thể ở vào.
Một Ôtômát được giả thiết là hoạt động trong một khung thời
gian rời rạc (discrete time frame).
Trạng thái kế (next state): là một trạng thái nội của đơn vị điểu khiển mà
nó sẽ ở vào tại thời điểm kế tiếp.
Tại một thời điểm bất kỳ đã cho, đơn vị điều khiển đang ở
trong một trạng thái nội (internal state) nào đó, và cơ cấu
nhập là đang quét (scanning) một kí hiệu cụ thể nào đó trên
input file.
Hàm chuyển trạng thái (transition function): là hàm gởi ra trạng thái
kế của ôtômát dựa trên trạng thái hiện hành, kí hiệu nhập hiện hành được
quét, và thông tin hiện hành trong bộ nhớ tạm.
Cấu hình (configuration): được sử dụng để tham khảo đến bộ ba thông
tin: trạng thái cụ thể mà đơn vị điều khiển đang ở vào, vị trí của cơ cấu
nhập trên thiết bị nhập (hay nói cách khác ôtômát đang đọc đến kí hiệu nào
của thiết bị nhập), và nội dung hiện hành của bộ nhớ tạm.
Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được
xác định bởi trạng thái kế (next state) hay bởi hàm chuyển
trạng thái (transition function).
Di chuyển (move): là sự chuyển trạng thái của ôtômát từ một cấu hình
này sang cấu hình kế tiếp.
Trong suốt quá trình chuyển trạng thái từ khoảng thời gian
này đến khoảng thời gian kế, kết quả (output) có thể được
sinh ra và thông tin trong bộ nhớ lưu trữ có thể được thay
đổi.
41
42
Phân loại dựa vào kết quả xuất ra của Ôtômát
Phân loại dựa vào hoạt động Ôtômát
Ôtômát đơn định (Deterministic Automata):
Accepter: là Ôtômát mà đáp ứng ở ngõ ra của nó
được giới hạn trong hai trạng thái đơn giản “yes”
hay “no”. “yes" tương ứng với việc chấp nhận chuỗi
nhập, "no" tương ứng với việc từ chối, không chấp
nhận, chuỗi nhập.
• Mỗi bước di chuyển chỉ được xác định duy nhất bởi
cấu hình hiện tại (hàm chuyển của Ôtômát là đơn trị)
Ôtômát không đơn định (Non-deterministic Automata):
• Tại mỗi bước di chuyển, nó có vài khả năng lựa chọn
để di chuyển (hàm chuyển của Ôtômát là đa trị). Việc
có vài khả năng lựa chọ thể hiện tính không đơn định
Transducer: là Ôtômát tổng quát hơn, có khả năng
sinh ra các chuỗi kí tự ở ngõ xuất. Máy tính số là
một Transducer điển hình.
43
44
11
Bài tập
Một vài ứng dụng
Cung cấp kiến thức nền tảng cho việc xây
dựng các ngôn ngữ lập trình (NNLT), các
trình dịch.
1. Tꢀm Ngôn ngữ L1 bao gồm các chuỗi từ
khóa begin, end của ngôn ngữ Pascal. Các
chuỗi biểu diễn cấu trúc lồng nhau của các
cặp từ khóa này trong các chương trình
trên ngôn ngữ Pascal
Dùng văn phạm để định nghĩa các NNLT.
Dùng Accepter để định nghĩa một vài thành
phần của NNLT.
2. Tꢀm Ngôn ngữ L2 bao gồm tập các danh
hiệu của Pascal
Xây dựng các bộ phân tích từ vựng, phân
tích cú pháp cho các NNLT.
45
46
Xây dựng văn phạm cho ngôn ngữ
Xác định ngôn ngữ của văn phạm
1. G1 có tập luật sinh là S → aSbS | bSaS | λ
2. G2 có tập luật sinh:
E → E + T | T
Ngôn ngữ L1, và L2 ở trên
L3 = {wwR | w ∈ {a,b}*}
n+m
L4 = {anbmc
| n,m ≥ 0}
L5 = {anbn+mcm | n,m ≥ 0}
T → T * F | F
F → (E) | a | b
47
48
12
12 trang
10620
Free
Bạn đang xem tài liệu "Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 2: Ngôn ngữ, văn phạm và ôtômát - Nguyễn Thị Thùy Linh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_otomat_va_ngon_ngu_hinh_thuc_chuong_2_ngon_ngu_van.pdf
