BÀI GING MÔN HC
LÝ THUYT ÔTÔMÁT & NNHT
Ging Viên: H Vn Quân
E-mail:

Web site: />Trng i hc Bách khoa
Khoa Công Ngh Thông Tin
Trang 2
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
NI DUNG MÔN HC
̈ Chng 1 Gii thiu v lý thuyt tính toán
̈ Chng 2 Ôtômát hu hn
̈ Chng 3 Ngôn ng chính qui và vn phm chính qui
̈ Chng 4 Các tính cht ca ngôn ng chính qui
̈ Chng 5 Ngôn ng phi ng cnh
̈ Chng 6 n gin hóa vn phm phi ng cnh và các
dng chun
̈ Chng 7 Ôtômát đy xung
̈ Chng 8 Các tính cht ca ngôn ng phi ng cnh
̈ Chng 9 Máy Turing
Trang 3
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
TÀI LIU THAM KHO
1. Bài ging lý thuyt Ngôn ng Hình thc và Automat -
H Vn Quân [2002].
2. An Introduction to Formal Languages and Automata -
Peter Linz [1990].
Trang 4
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
HÌNH THC ÁNH GIÁ
̈ S có thông báo c th cho tng khóa hc. Tuy nhiên,

̈ nh ngha
̈ Phân loi ngôn ng
̈ Quan h vi ôtômát
̈ ng dng vào vic xây dng các ngôn ng lp trình
̈
Trang 8
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Yêu cu v kin thc nn
̈ Lý thuyt
̈ Tp hp
̈  th
̈ K thut chng minh
̈ Qui np
̈ Phn chng
̈ K thut mô phng
Trang 9
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Ba khái nim c bn
̈ Ngôn ng (languages)
̈ Vn phm (grammar)
̈ Ôtômát (automata)
Trang 10
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Ngôn ng
̈ Ngôn ng là gì?
̈ Các t đin đnh ngha ngôn ng mt cách không chính xác là
mt h thng thích hp cho vic 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 qui tc
đ vn dng chúng.
̈ nh ngha trên cha đ chính xác đ nghiên cu v

a
2
a
n
và v = b
1
b
2
b
m
là chui:
wv = a
1
a
2
a
n
b
1
b
2
b
m
̈ Ðo (reverse), w
R
̈ Ðo ca chui w = a
1
a
2
a

̈ Ly tha (power), w
n
̈ w là mt chui thì w
n
là mt chui nhn đc bng cách kt ni
chui w vi chính nó n ln.
̈ w
0
= λ
321
L
laàn n
n
www =
Trang 16
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Các khái nim (tt)
̈ Σ*, Σ
+
(bao đóng sao và bao đóng dng)
̈ Σ* là tp tt c các chui trên Σ k c chui trng.
̈ Σ
+
là tp tt c các chui trên Σ ngoi tr chui trng.
̈ Σ* = Σ
+
∪ {λ} ; Σ
+
= Σ* - {λ}
̈ Σ thì hu hn còn Σ

1
, L
2
. Kt ni ca 2 ngôn ng L
1
, L
2
là:
L
1
L
2
= { xy : x ∈ L
1
, y ∈ L
2
}
̈ Ly tha, L
n
̈ Ly tha bc n ca L, kí hiu là L
n
, là vic kt ni L vi chính
nó n ln
̈ L
0
= {λ}
L
L
321
L

2
∪
̈ Bao đóng dng (positive closure) ca L
̈ Kí hiu là L
+
L
+
= L
1
∪ L
2
∪ L
3
∪
Trang 20
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Vn phm
̈ 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.
̈ Ví d
̈ Cho đon vn phm ting Anh sau
<sentence> → <noun phrase><predicate>,
<noun phrase>→ <article><noun>,
<predicate> → <verb>,
<article> → a | the,
<noun> → boy | dog,
<verb> → runs | walks,
Trang 21

Vn phm (tt)
̈ 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 phi đc phát biu khác đi.
̈ 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 là terminal
hoc bin.
̈ Các kí t ch thng u, v, w, x, y, z biu th chui các terminal.
̈ Các kí t ch thng Hi Lp α, β, γ biu th chui các bin và
các terminal.
Trang 24
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Các khái nim
̈ Dn xut trc tip (directly derive), ⇒
̈ Cho lut sinh x → y và chui w = uxv .
̈ Lut sinh trên có th áp dng ti chui w. Khi áp dng ta s
nhn đc chui mi
z = uyv
̈ w dn xut ra z hay ngc li z đc dn xut ra t w và kí
hiu là:
uxv ⇒ uyv
Trang 25
Lý thuyt Ôtômát & NNHT - Khoa Công Ngh Thông Tin
Ngôn ng đc sinh ra bi vn phm
̈ Dn xut gián tip ,
̈ Nu w
1
⇒ w
2