20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
ĐỀ CƯƠNG AUTOMAT
Câu 1 : Khái niệm về ngôn ngữ,từ(chuỗi,xâu) 1 số phép toán cơ bản trên từ và
trên ngôn ngữ.Các hình thức biểu diễn ngôn ngữ?Cho ví dụ minh họa?
Ngôn ngữ : theo từ điển, 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 tập các ký hiệu, các qui tắc để vận dụng
chúng.
Một ngôn ngữ (hình thức) L trên bộ chữ cái ∑ là một tập hợp các chuỗi từ các ký
hiệu của bộ chữ cái ∑
∑* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng ε, sinh ra từ bộ chữ cái ∑
∑
+
: tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra từ bộ chữ cái ∑
∑* = ∑
+
+ {ε} ∑+ = ∑* - {ε}
Từ : Cho ∑={a1,a2….am} ,1 dãy α=ai1ai2……ait (aij € ∑) được gọi là 1 từ hay
1 xâu(chuỗi ) trên bảng ∑
Note: ∑ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ
cái.Mỗi 1 phần tử thuộc ∑ được gọi là 1 chữ cái hay 1 ký hiệu
1 số phép toán cơ bản trên từ:
Chuỗi nối kết : chuỗi được tạo thành bằng cách viết chuỗi thứ nhất sau đó viết
chuỗi thứ 2…… ε là đơn vị của phép nối kết
• Chuỗi đảo ngược : chuỗi đảo ngược của W là W
R
,là chuỗi được viết theo thứ
tự ngược lại
• Phép cắt trái : của từ α cho từ β - là phần còn lại của từ α sau khi cắt bỏ
phần đầu β trong từ α.

2
LLL…LL = L
i
(kết nối i lần trên cùng ngôn ngữ L) L
0
= {ε}
• Ngôn ngữ lặp (bao đóng Kleenr hoặc Closure)

• Ngôn ngữ lặp cắt (bao đóng dương – positive closure)
• Ngôn ngữ ngược.
• Ngôn ngữ cắt trái của ngôn ngữ X cho ngôn ngữ Y
• Ngôn ngữ cắt phải của ngôn ngữ X cho ngôn ngữ Y

Các hình thức biểu diễn ngôn ngữ :
• Liệt kê các phần tử (chuỗi) : L={aa,ab,bb}
• Mô tả các đặc điểm chủ yếu : L={a
i
| I là số nguyên tố}
• Biễu diễn ngôn ngữ 1 cách tổng quát thông qua văn phạm (grammar) và
automata.
Văn phạm : là cơ chế sinh ra mọi chuỗi của ngôn ngữ
Automata : là 1 máy trừu tượng hay 1 cơ chế cho đoán nhận 1 chuỗi bất kỳ
có thuộc 1 ngôn ngữ L hay không
(các ví dụ xem trong bài giảng)
Câu 2 : Định nghĩa văn phạm,dẫn xuất và ngôn ngữ sinh bởi văn
phạm.Cho ví dụ minh họa
 Theo từ điển, văn phạm là một tập các quy tắc về cấu tạo từ và các quy tắc về
cách thức liên kết từ lại thành câu.
 Ví dụ đơn giản về văn phạm:
{ }

*
\ | ,Z Y X z x X y Y mà x yz= = ∈Σ ∈ ∈ =
{ }
/ | ,Z X Y z x X y Y mà x zy
∗
= = ∈Σ ∈ ∈ =
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
<câu>→<chủngữ><vịngữ>
<chủngữ>→tôi | anh | chị
<vịngữ>→<độngtừ><danhtừ>
<độngtừ>→ăn | uống
<danhtừ>→cơm | phở | sữa | café.
Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần G = < Σ, Δ, S, P >, trong đó:
• Σ - bảng chữ cái, gọi là bảng chữ cái cơ bản (bảng chữ cái kết thúc –
terminal symbol);
• Δ , Δ ∩ Σ =Ø, gọi là bảng ký hiệu phụ (báng chữ cái không kết thúc –
nonterminal symbol);
• S ∈ Δ - ký hiệu xuất phát hay tiên đề (start variable);
• P - tập các luật sinh (production rules) dạng α→β, α, β ∈ (Σ ∪ Δ)*, trong α
chứa ít nhất một ký hiệu không kết thúc (đôi khi, ta gọi chúng là các qui tắc
hoặc luật viết lại).
Dẫn xuất :
 Nếu A → b là luật sinh trong văn phạm G và γ, � là 2 chuỗi bất kỳ, thì
khi áp dụng luật sinh A → b vào chuỗi γA� ta sẽ thu được chuỗi γb�
 Dẫn xuất trực tiếp: nếu α→β là một luật sinh thì
 Dẫn xuất gián tiếp: nếu các chuỗi a
1
, a

chất của các luật sinh.
 Văn phạm loại 0 (văn phạm không hạn chế-

UG – 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;
20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
Vn phm loi 1 (vn phm ng cnh CSG-Context Sensitive Grammar) :
nu vn phm G cú cỏc lut sinh dng v :
,||||
Vn phm loi 2 (vn phm phi ng cnh - CFG Context-Free Grammar) :
cú lut sinh dng A vi A l mt bin n v l chui cỏc ký hiu
thuc ( )
*
Vớ d : G=({a, b}, {S, A, B}, P, S) vi P gm cỏc lut sinh:
S -> AB
A -> aA|a
B -> bB|b
Vn phm loi 3 (Vn phm chớnh quy -

RG Regular Grammar) : cú mi
lut sinh dng tuyn tớnh trỏi hoc tuyn tớnh phi
Tuyn tớnh phi: A wB hoc A w;
Tuyn tớnh trỏi: A Bw hoc A w;
Vi A, B l cỏc bin n, w l chui ký hiu kt thỳc (cú th l rng).
(vớ d xem trong bi ging)
Cõu 4 : Cho vn phm phi ng cnh G = < , , S, P > hóy ch ra rng xõu w
khỏc rng nm trong L(G) khi tn ti cõy dn xut trong vn phm G m cỏc
nỳt lỏ ca nú to nờn xõu w

1
, G
2
sinh ra L.
Ta xây dung Văn phạm G nh sau:
1. N:= N
1


N
2
{S},
2. S không thuộc N
1
,

N
2
3. T:=T
( )
, , , ,A A



=
20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
4. Tập luật sinh P đợc xác định:
P:= P


là w L
1
L
2
.
Cõu 6 : Chng minh ngụn ng sinh ra bi vn phm l úng vi phộp ghộp
(ni kt)
Từ các văn phạm trên ta xây dựng G sao cho L(G)=L
1
.L
2
nh sau: G=(N,T,S,P) trong
đó T:=T
1
T
2
, N:=N
1
N
2
{S}, P:=P
1
P
2
{S S
1
S
2
}.

- Ta mô tả các tính chất trên thông qua ví dụ sau: Cho văn phạm G
1
=(N
1
,T,S
1
,P
1
),
G
2
=(N
2
,T,S
2
,P
2
) là 2 văn phạm cùng loại trong đó N
1
={S
1
}, T
1
={a,

b}, P
1
={ S
1
ab, S

3
)= L(G
1
)
L(G
2
);
L(G
3
)= L(G
1
). L(G
2
).
1.
2. Ta đã biết L(G
1
)={a
n
b
n
, n>=1}, L(G
2
)={c
m
, m>=1}

. Ta chứng minh L(G
3
)=

cS
2
, S
2
c}.
- Giả sử wL(G
3
) khi đó tồn tại dãy dẫn xuất S*w (ứng với S*w
1
w
2
w
3
w
k
=w). Để có thể nhận đợc w thì w
1
chỉ có thể là S
1
hoặc S
2
. Nếu w
1
là S
1
w
2
=a
2
S

L(G
2
) ta có thể coi w L(G
1
) khi đó tồn tại dãy dẫn
xuất trong G
1
có dạng S
1
*w (ứng với S
1
*w
1
=aS
1
b w
2
= a
2
S
1
b
2
w
3

w
k
=a
n

2. Ta xây dựng G
3
sao cho L(G
3
)= L(G
1
). L(G
2
)={a
n
b
n
c
m}
}.
N:={S, S
1
,S
2
}, T:={a,b,c}, P:={ SS
1
S
2
, S
1
ab, S
1
aS
1
b, S

S
1
b
2
S
2
w
3

w
k
=a
n
b
n
S
2
a
n
b
n
c S
2
a
n
b
n
c
m-1
S

2
trong đó w
1
L(G
1
) ,w
2
L(G
2
) vì vậy tồn tại dẫn xuất S
1
*w
1
và
S
2
*w
2
. Lập dẫn xuất mới
20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
SS
1
S
2
aS
1
bS
2

=w , đây là dẫn
xuất trong L(G
3
), từ đây suy ra điều phải chứng minh.
Cõu 7 : Cho G=< , , S, P > khụng phi l vn phm loi 0 vi ký t xut
phỏt S cú v phi ca quy tc dn xut.Ch ra rng tn ti vn phm
G=< , , S, P >cựng loi v tng ng vi G khụng cú ký t xut phỏt
v phi ca quy tc dn xut
Chứng minh. Xây dựng G=(N,T,S,P) nh sau:
- N:=N{S}, ở đây S là ký hiệu mới cha có trong N và T
P:=P{ S/SP, (NT)
+
}, nghĩa là P gồm các quy tắc của G bổ sung
thêm các quy tắc dạng S nếu trong P có quy tắc S. Với quy ớc trên ta thấy
- Không có quy tắc nào mà ký tự xuất phát xuất hiện ở vế phải của dẫn xuất.
Giả sử wL(G) khi đó tồn tại dãy dẫn xuât S* w và tồn tại (NT)* sao cho
S* w. Theo cách xây dựng dẫn xuất vì trong G có S nên trong G có
S vì vậy dẫn xuất S* w là dẫn xuất trong G vậy nên wL(G) do đó
L(G) L(G).
Ngợc lại nếu wL(G) nghĩa là S*w tồn tại (NT)* S* w mà S*
có tơng ứng S2fg trong G vậy nên S*w là dẫn xuất trong G cho nên
L(G) L(G).
Nhn xột : chúng ta coi các văn phạm loại 1,2,3 không có các ký tự xuất phát nằm
ở vế phải của các dẫn xuất và do eL(G) nên trong luật sinh phải có Se.
20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
Cõu 8 : Khỏi nim vn phm phi ng cnh?Khỏi nim v dn xut v cõy dn
xut?S nhp nhng ca vn phm?
Vn phm phi ng cnh : cú lut sinh dng A vi A l mt bin n v l

A
2m
w
1
w
2
w
l
, xây dựng cây thoả điều kiện
sau:
- Bơc 0: Xây dựng gốc có nhãn S
- Bớc 1: Các đỉnh con của S là các ký tự đợc sinh ra do áp dụng luật sinh thứ 1.
(Đó là A
11
A
12


A
1n
-
Bớc 2. Các đỉnh con của A
1j
j =1 n
.
: Là những ký tự đợc sinh ra do áp dụng luật
sinh thứ 2
- Bớc i: Giả sử đã xác định đợc các đỉnh ở bớc i-1, các đỉnh con đợc sinh ra ở bớc
thứ i là các đỉnh sinh ra từ các đỉnh ở bớc thứ i-1 khi áp dụng luật sinh thứ i.
20

Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
 Quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân
luôn được thực hiện ưu tiên hơn phép cộng
Câu 9 : Cho văn phạm phi ngữ cảnh G=< Σ, Δ, S, P > không chứa xâu
rỗng.Trình bày giải thuật loại bỏ các ký hiệu thừa ,loại bỏ luật sinh 𝞮,luật
sinh đơn vị
Các yếu tố thừa :
 Các ký hiệu không tham gia vào quá trình dẫn xuất ra chuỗi ký hiệu kết
thúc;
 Luật sinh dạng A → B (làm kéo dài chuỗi dẫn xuất).
Khái niệm văn phạm rút gọn :
vẫn giữ khả năng sản sinh ngôn ngữ đó mà không chứa những yếu tố vô ích không
sinh ra chuỗi, làm phức tạp hay kéo dài dẫn xuất sinh chuỗi.
 Loại bỏ các ký hiệu thừa :
Định nghĩa :
1 ký hiệu X được gọi là có ích nếu có 1 dẫn xuất dạng S → *αXβ → *w với α,β
là các chuỗi bất kỳ và w⋲ ∑*
Bổ đề 1:
Cho CFG G=< Σ, Δ, S, P > với L(G)≠ ⌀ có 1 CFG G=< Σ’, Δ’, S, P’ > tương
đương sao cho mỗi A thuộc Δ’ tồn tại w thuộc ∑* để A→ *w
 Có thể loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
Giải thuật tìm ký hiệu phụ :
1.Old Δ’ :=⌀ ;
2. new Δ’ :={A|A → w với w thuộc T*}
3.while (Old Δ’ ≠ New Δ’)
do{

2………
X
n
với mọi X
i
⋲ Ω thì thêm B vào Ω;
 B2 : xây dựng P’ với mỗi A→X
1
X
2………
X
n
trong P ta xây dựng luật sinh A→
α1,α2…,αn với điều kiện :
Nếu X
i
⋶ Ω thì αi = X
i
Nếu X
i
⋲ Ω thì αi = X
i
|�
Không phải thì tất cả αi đều bằng �;
 Luật sinh đơn vị :
Mỗi CFL không chứa ε được sinh ra bởi CFG không có ký hiệu vô ích, không
có luật sinh ε hoặc luật sinh đơn vị.
 Loại bỏ được các luật sinh đơn vị
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn

X
2………
X
n
với mọi X
i
⋲ Ω thì thêm B vào Ω;
 B2 : xây dựng P’ với mỗi A→X
1
X
2………
X
n
trong P ta xây dựng luật sinh A→
α1,α2…,αn với điều kiện :
Nếu X
i
⋶ Ω thì αi = X
i
Nếu X
i
⋲ Ω thì αi = X
i
|�
Không phải thì tất cả αi đều bằng �;
Câu 11 : định nghĩa luật sinh 𝞮. Cho văn phạm phi ngữ cảnh G=< Σ, Δ, S, P >
không chứa xâu,không chứa các ký hiệu thừa.Trình bày giải thuật loại bỏ luật
sinh đơn vị ?
 Luật sinh đơn vị :
Mỗi CFL không chứa ε được sinh ra bởi CFG không có ký hiệu vô ích, không

B1. Thay thế tất cả các luật sinh có độ dài vế phải là 1 (loại bỏ các luật sinh đơn
vị và ε)
B2.Thay thế tất cả các luật sinh có độ dài vế phải lớn hơn 1 và có chứa ký hiệu
kết thúc
A→ X
1
X
2…
X
i……
X
n
; a→X
i
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
A→ X
1
X
2…
C
a……
X
n
; C
a
→a
B3.Thay thế các luật sinh mà vế phải có nhiều hơn 2 ký tự chưa kết thúc


B | b
C
a
→ a; C
b
→ b
Bước 3 : thay thế các luật sinh có độ dài vế phải > 2:
A → B
1
B
2
B
m
(m>2)
A → B
1
D
1
D
1
→ B
2
D
2

D
m-2
→ B
m-1
B

 G không chứa các ký hiệu thừa;
 G không chứa các luật sinh đơn vị.
 Các luật sinh của nó có dạng A → aα (α là chuỗi các biến hoặc ε nếu ε ∉ L,
ngược lại thêm vào luật sinh S → ε).
Bổ đề 1:
Cho G(Σ, Δ, S, P) là một CFG, đặt A → α
1
Bα
2
là luật sinh trong P và B → β
1
|β
2
| |
β
r
là các B - luật sinh;
Văn phạm G
1
(Σ, Δ
1
, S, P
1
) thu được từ G bằng cách loại bỏ luật sinh A → α
1
Bα
2
và
thêm vào các luật sinh A→ α
1

là
các A - luật sinh còn lại; G
1
(Σ, Δ ⋃ {B}, S, P
1
) là CFG được tạo thành bằng
cách thêm biến mới B và thay các A - luật sinh bằng các luật dạng
A → β
i
; A → β
i
B; (1 ≤ i ≤ s)
B → α
i
; B → α
i
B; (1≤i≤r)
thì ta có G
1
tương đương G, hay L(G) = L(G
1
).(loại bỏ VP đệ quy trái)
Các bước chuyển văn phạm phi ngữ cảnh về dạng chuẩn Greibach
Đặt G là CFG sinh ra CFL không chứa ε
Bước 1: xây dựng G' có dạng GNF tương đương G
Bước 2: đổi tên các biến trong G' thành A
1
, A
2
, , A

, ,B
i-1
}))*
Bước 4 : thay thế các A
i
– luật sinh về đúng dạng(áp dụng bổ đề 1)
Bước 5 : thay thế các B
k
– luật sinh về đúng dạng (áp dụng bổ đề 1)
Câu 15.Trình bày về Automat hữu hạn.Phân biệt các dạng Automat hữu hạn?
Ngôn ngữ đoán nhận bởi Automat hữu hạn.VD minh họa
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
 Automata là một mô hình toán học hay máy trừu tượng có cơ cấu và hoạt
động đơn giản nhưng có khả năng đoán nhận ngôn ngữ.
 Một finite automata (FA) là một mô hình tính toán hữu hạn: mọi cái liên
quan đến nó đều có kích thước hữu hạn cố định và không thể mở rộng trong
suốt quá trình tính toán;
 Một FA làm việc theo thời gian rời rạc (time steps);
 Nói chung, thông tin ra sản sinh bởi một FA phụ thuộc vào cả thông tin vào
hiện tại lẫn các thông tin vào trước đó. Nếu sử dụng bộ nhớ (memory), giả
sử rằng nó có ít nhất một bộ nhớ vô hạn về tiềm năng;
 Sự phân biệt giữa các loại automata khác nhau chủ yếu dựa trên việc thông
tin có thể được đưa vào memory hay không;
Các dạng Automat hữu hạn : Đơn định và đa định
Phân biệt :
 DFA (hữu hạn đơn định) tại một thời điểm với một trạng thái và một ký tự
nhập vào thì máy chỉ có thể chuyển đến không nhiều hơn một trạng thái.
 NFA (hữu hạn đa định) là automata mà ứng với một trạng thái và một ký tự

20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
X -Tập hữu hạn các ký hiệu vào
Y - Tập hữu hạn các ký hiệu ra
S - Tập hữu hạn gọi là tập các trạng thái
- ánh xạ từ XxSS gọi là hàm chuyển trạng thái.
- ánh xạ từ SY gọi là hàm đa thông tin ra.
Đợc gọi là Automat Moore
Với định nghĩa trên ta hiểu Automat Moore hoạt động theo cơ chế tín hiệu phát ra
phụ thuộc trạng thái nhận tín hiệu.
Cõu 17 : Trỡnh by cỏc phng phỏp biu din Automat hu hn?Cho vớ d
Cho mt automata thc cht l cho hm chuyn trng thỏi ca nú, cú th cho di
dng bng chuyn trng thỏi hoc cho di dng th chuyn.
Cú 2 cỏch biu din Automat l qua bng chuyn v th di chuyn
th chuyn l mt a th cú hng (cú th cú khuyờn) G: Tp nh ca G
c gỏn nhón bi cỏc phn t thuc Q, cỏc cung c gỏn nhón bi cỏc phn t
thuc , nu a , p,q Q v (q, a) = p thỡ s cú mt cung t nh q ti nh
p c gỏn nhón a. nh vo ca th chuyn ng vi trng thỏi ban u q
0
.
Bng chuyn bng cú kớch c |Q| ì ||, trong ú dũng i ct j ca bng l
hoc b trng.
Vớ d :
( )
,
i j
q a

20

}. Hµm chuyÓn cã d¹ng sau:
20
Automat v ngụn ng hỡnh thc..Ngụ Vn
Lng - TH
Trạng thái Ký tự vào
0 1
s
0
{s
0
, s
3
}

{s
0
, s
1
}
s
1
e

s
2
s
2
s
2
s

) trong đó w
1
là ký tự đầu
tiên của xâu w.
- Đối với đỉnh s* (s
0
,w
1
) ta xây dựng các đỉnh con của nó là các đỉnh thuộc tập
(s*,w
2
) và cứ tiếp tục cho đến ký tự cuối cùng của xâu.
- Trong cây này nếu có một đờng đi từ s
0
đến một lá chứa trạng thái kết thúc thì ta
nói máy M đoán nhận đợc xâu vào đang xét, ngợc lại ta nói M không đoán nhận đ-
ợc xâu vào đó. Với xâu vào có dạng w=01001 máy M có cây đoán nhận đi từ s
0
đến s
4
F nên máy M đoán nhận xâu trên.
s
0
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
0 0
1 1
0 0
0 0 0

0
];
o F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết
thúc trong tập F của A;
o Hàm chuyển δ’([q
1
, q
2
, , q
i
], a) = [p
1
, p
2
, , p
j
] nếu và chỉ nếu δ({q
1
,
q
2
, , q
i
}, a) = {p
1
, p
2
, , p
j
}.

4
20
Automat và ngôn ngữ hình thức……………………………………………………………….……….Ngô Văn
Lương - ĐTH
Ví dụ : NFA A({q
0
, q
1
}, {0, 1}, δ, q
0
, {q
1
}).Xây dựng DFA tương đương
A’ (Q’, {0, 1}, δ’, [q
0
], F’); Q’ = {⌀, [q
0
], [q
1
], [q
0
, q
1
]} ; F’ = {[q
1
], [q
0
, q
1
]}

]
δ’([q
0
, q
1
], 1) = [q
0
, q
1
]
Câu 20 : Trình bày phương pháp biến đổi từ NFA𝞮 về NFA.Ví dụ minh họa
nếu L được chấp nhận bởi một NFA𝞮 thì L cũng được chấp nhận bởi một NFA
không có 𝞮-dịch chuyển.
phương pháp biển đổi :
 Giả sử ta có NFA𝞮 A(Q, Σ, δ, q
0
, F) chấp nhận L,
 Ta xây dựng: NFA A’={Q, Σ, δ’, q
0
, F’}, với:
1. F’ = F q⋃
0
nếu 𝞮*( q
0
) chứa ít nhất một trạng thái thuộc F. Ngược
lại, F’ = F;
2. δ’(q, a) = δ*(q, a).
Giải thuật xây dựng hàm chuyển tương đương :
Tìm kiếm T = �* (q
0