TRƢỜNG ĐẠI HỌC HÀNG HẢI
BỘ MÔN: KHOA HO
̣
C MA
́
Y TI
́
NH
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMAT
45
45
0
0
0
0
Điều kiện tiên quyết:
Mục tiêu của học phần:
-
-
Nội dung chủ yếu
Gồm các phần:
-
-
-
-
Nội dung chi tiết của học phần:
TÊN CHƢƠNG MỤC
PHÂN PHỐI SỐ TIẾT
03
01
2.12. Ngôn ng Otomat
ii TÊN CHƢƠNG MỤC
PHÂN PHỐI SỐ TIẾT
TS
LT
4.2.4.
4.2.5.
4.3.
4.4.
Nhiệm vụ của sinh viên :
Tài liệu học tập :
- Ngôn ngữ hình thức
- Lý thuyết otomat và thuật toán
- Ngôn ngữ hình thức
- Giáo trình chương trình dịch
- Phân tích cú pháp
Hình thức và tiêu chuẩn đánh giá sinh viên:
-
-
Thang điểm: Thang điểm chữ A, B, C, D, F
Điểm đánh giá học phần: Z = 0,2X + 0,8Y.
Chƣơng 2: Ngôn ngữ chính quy và Otomat hữu hạn
9
9
2. 2
10
18
26
30
30
30
31
31
31
31
2. 12. -
31
31
Chƣơng 3: Ngôn ngữ phi ngữ cảnh và Otomat đẩy xuống
60
62
63
64
Otomat
1
CHƢƠNG 1: VĂN PHẠM VÀ NGÔN NGỮ
Kiến thức cơ bản:
1.1. Bảng chữ cái, từ, ngôn ngữ
1.1.1.
2
= ac, | a
1
| = 4, |a
2
| = 2
Otomat
2
, thì a
. = {0,1} ,
a
1
=
0110 , a
*.
+
+
=
*
\ {}
1.1.3.
( a
i
)
và .
= . = a
1
a
2
a
3
n
a
1
a
2
m
={0,1}
= 011, =1101
= 0111101
+
+
() = ()
Otomat
3
Z
/y = 10
1.2.3.
= a
1
a
2
m-1
a
m
*
= a
m
a
m-1
2
a
1
| | = | |
1.3. Các phép toán trên ngôn ngữ
C = A B = {x */x B}
= {a,b,c}
A = {a, b, ab, ac, cb}, B = {aa, bb, cc}
-
A.(B.C) = (A.B).C
-
A.(B C) = (A.B) (A.C)
Otomat
5
-
n
1.3.4.
C = A\B = {x * | x A, x B}
= {a, b, c}
A = {a, b, ac, bc, aa}, B = {b, bc, ab, bb}
C = B\A = {b, ab, bb}
1.3.5.
A = C
B
= { x */ x B}
Cho B = {a, bc}.
A = {x * | x a, x bc}.
1.3.6.
.
n
-
(A
*
)* = A
*
-
{}
*
= {}
-
()
*
= {} . }
-
()
+
= .
1.4. Văn phạm
1.4.1. Định nghĩa văn phạm cấu trúc (Grammar)
và c
1) Văn phạm loại 0:
văn phạm không hạn chế (Unrestricted Grammar)
2) Văn phạm loại 1: ||<|| thì G
văn phạm cảm ngữ cảnh CSG (Context-Sensitive
Grammar)
3) Văn phạm loại 2: là
(V văn phạm phi
ngữ cảnh CFG (Context-Free Grammar)
4) Văn phạm loại 3tuyến tính phải (rightlinear): A
ó
tuyến tính trái (left-linear): A
Otomat
8
văn phạm chính quy RG (Regular Grammar)
Ta có : L3 L2 L1
1.6. Các ví dụ về văn phạm
Cho
12
, , ,
n
a a a
cho L
2
1
.
Bài 2
L = {a
n
b
2n+1
c
k
*n > 0, k 0}
Otomat
9
CHƢƠNG II: NGÔN NGỮ CHÍNH QUY VÀ OTOMAT HỮU HẠN
2.1. Nguồn và ngôn ngữ đƣợc sinh bởi nguồn
2.1.1.
O)
□)
{}.
2
S
1
S
2
S
3
S
4
S
5
a
b,c
a,c
b,a
c
a
1
Otomat
10 2. 1. 5.
-
-
= {bbc
s
,bac
s
,cbc
s
,cac
s
N
I
(s
1,
s
2
) = {a} N
I
(s
1
,s
4
).{a} = {a}. {bbc
s
a,bac
s
a,cbc
s
a,cac
s
a}
aa,cbc
s
aa,aa,bbc
s
ac,bac
s
ac,cbc
s
ac,cac
s
1
là :
N(I
1
) = N
I
(s
1
,s
4
) N
I
(s
1
,s
5
) = {bbc
s
s
, bbc
t
aa,
bac
t
aa, cbc
t
aa, cbc
t
aa, bbc
t
ac, bac
t
ac, cbc
t
ac, cac
t
ac
2.2. Các phép toán trên nguồn
2.2
Thuật toán đơn định hoá nguồn như sau:
1)
T
1
(s,a) = {u D(I) |a N(s,u)}.
H
2. 2. 2.
1.
S
0
S
1
S
2
a,b
a
b
b
b
a
a
b
b
q
0
q
1
q
2
q
3
a
a
a
b
a
b
a
b
Otomat
12
và I
2
1
và I
2
, thêm
1
2
1
) và v(I
2
).
1
) F(I
2
).
1
) N(I
2
).
Chú ý: Ta có th
1
I
1
và I
2
là :
1
và I
2
q
0
q
1
q
2
b
a
c
S
0
2
b
a
c
S
1
Otomat
13
2.2.4.
1
, I
2
I
1
, I
2
1
) N(I
2
1
, I
1
)
và R F(I
2
) .
1
, I
2
sinh ra.
1
và I
2
(hình 1.5 )
S
0
, q
Otomat
14
2.2.5.
1
, I
2
1
, I
2
1
).N(I
2
).
1
, I
2
.
Thuật toán xây dựng nguồn tích ghép:
sinh ra.
1
và I
2
(hình 1.5)
:
2.2.6.
1
1
1
Thuật toán xây dựng nguồn lặp I:
1
S
1
S
2
Hình 1.8. Tích ghép 2
1
và I
2
Otomat
15
1
1
)
1
1
1
1
1
.
Thuật toán xây dựng nguồn soi guơng:
1
sau:
1)
1
.
2)
1
(v(I
1
F(I) = {v(I
1
)};
3)
1
S
0
S
2.2.8. Phép chia trái
1
, I
2
1
, I
2
1
, I
2
.
Thuật toán xây dựng nguồn thương bên trái:
1)
1
, I
2
.
2)
v(K);
3)
1
);
4) S (S
A(I
s
i
i
(v(I
s
i
)
= s
i
) và F(I
s
i
) = F(I
1
)
N(I
1
)
N(I
2
)
S
1
a
c
b
S
2
.
3)
1
và I
2
.
-
1
v(I
1
) .
-
i
D(I
1
s
i
)
I
1
,I
2
=
N(I
1
)
-
: Q Q.
-
0
trạng thái đầu
trạng thái cuối.
-
*
0
1
1
0
0
1
1
1
Q
Otomat
19
0
q
3
0
q
2
q
3
q
0
q
1
1
q
1
q
0
q
3
q
2
1
0
0
q
0
110101
q
1
q
0
q
2
q
3
q
1
110101
110101
110101
110101
110101
110101
q
0
Otomat
20
Vì q
0
n
S
0
x
1
x
2
n
S
1
x
2
n
S
n
x
n
S
n+1
0
0
n+1
0
S
1
S
2
c
S
1
S
2
S
2
x
q
Otomat
21
Quá trình
S
0
aabccb S
1
abccb S
0
0
, , F}
S
0
: S x S)
F
Ví
0
, t
1
, t
2
}, {0, 1}, {t
0
}
, , {t
1
,t
2
}
t
0
SSi
Si
)
(Q, ax)= ( (Q,a),x) , a , x
*
Copyright: Tài liệu đại học ©