Mục Lục

MỞ ĐẦU
Lý thuyết automat và ngôn ngữ hình thức đóng một vai trò rất quan trọng

trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong
việc xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các
ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán
cả cho dạng thông tin vào ra lẫn kiểu thao tác. Vì thực chất của nó là một lĩnh
vực khoa học liên ngành, nhu cầu mô tả hình thức văn phạm được phát sinh
trong nhiều ngành khoa học khác nhau từ ngôn ngữ học đến sinh vật học. Chính
1


vì vậy, đối với những người trong lĩnh vực công nghệ thông tin thì việc tìm hiểu
các khái niệm về lý thuyết automat và ngôn ngữ hình thức là không thể thiếu.
Cũng chính vì vậy, ngôn ngữ hình thức được đưa vào làm môn học cơ sở chuyên
ngành cho tất cả các sinh viên công nghệ thông tin.
Đây là môn học cơ bản, mang tính phức tạp, trừu tượng cao. Chính vì
vậy, khi gặp những giải thuật phức tạp thì các lời giải hàn lâm sẽ rất buồn tẻ và
dễ gây nhàm chán. Vì vậy, nếu như có thể xây dựng một bộ công cụ hỗ trợ trong
việc giảng dạy môn automata và ngôn ngữ hình thức với ứng dụng trực tiếp
trong công tác học tập thì em tin chắc rằng nó có thể giúp các bài giảng bộ môn
Automata và ngôn ngữ hình thức phong phú và sinh động hơn. Dựa trên ý tưởng
trên, cùng với sự hướng dẫn, giúp đỡ nhiệt tình của thầy giáo Hà Chí Trung em
tham gia nghiên cứu đề tài: “Tìm hiểu và xây dựng chương trình mô phỏng
các thuật toán hỗ trợ học tập và giảng dạy môn học automata và ngôn ngữ
hình thức”.
Hình thức làm bài em sẽ mô tả cụ thể và chi tiết vào phần dưới và em sử
dụng hoàn toàn bằng ngôn ngữ lập trình C#.
Lúc mới nhận đề tài em dự định và mong muốn làm được tất cả các phần

Automat, văn phạm, các thuật toán có liên quan. Sau đã tìm hiểu thì xây dựng
chương trình để giải quyết yêu cầu của bài toán.

3


Chương 2. CƠ SỞ LÝ THUYẾT
2.1. Ngôn ngữ hình thức
2.1.1. Khái niệm ngôn ngữ hình thức
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 S là một tập hợp các chuỗi từ
các ký hiệu của bộ chữ cái S.
Trong đó:
S* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng ε, sinh ra S.
S+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra S.
S* = S+ + {ε}

S+ = S* - {ε}

Cách biểu diễn ngôn ngữ: Có ba cách:
Liệt kê các phần tử chuỗi. Ví dụ biểu diễn các phần tử của ngôn ngữ L
gồm các chuỗi aa,aba,baa,baba như sau: L = {aa, aba, baa, baba}
Mô tả ngôn ngữ thông qua đặc điểm chủ yếu. Ví dụ một ngôn ngữ gồm
các chuỗi có chữ cái a và theo sau là số nguyên tố biểu diễn như sau: L = {ai | i
là số nguyên tố}
Biểu diễn ngôn ngữ một cách tổng quát thông qua văn phạm và automata.
Đó là cơ chế sản sinh và cơ chế đoán nhận. Trong đó:
Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ.

Chuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi w được viết theo thứ
tự ngược lại.
Ví dụ: chuỗi w = abcd đả ngược của w là wR = dcba và ta có εR = ε.
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ừ α.
Phép cắt phải: của từ α cho từ β là phần còn lại của từ α sau khi cắt bỏ
phần đuôi β trong từ α.
2.2. Văn phạm
2.2.1. Khái niệm văn phạm
Văn phạm: theo từ điển 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.
5


Định nghĩa 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. Tập các kí hiệu kết thúc.
Δ: (Δ ∩ Σ =Ø), gọi là bảng ký hiệu phụ. Tập các kí hiệu không kết thúc.
S ∈ Δ: Được gọi là biến khởi đầu(kí hiệu mục tiêu)
P: tập hữu hạn các luật sinh dạng α→β, trong đó:α, β ∈ (Σ ∪ Δ)* 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).
Ví dụ
Cho văn phạm sau:
G = ({a, b},{S, A, B},, S, P)
Trong đó P là các luật sinh có dạng:
S → aAS | bBS | λ,
A → aaA | b,
B → bbB | a,
2.2.2.Các khái niệm liên quan

sinh dạng α→β và ,|β| ≥ |α| ví dụ:
Văn phạm loại 2: (văn phạm phi ngữ cảnh) là văn phạm 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ăn phạm loại 3: (văn phạm chính quy) có mọi luật sinh dạng tuyến tính
phải hoặc tuyến tính trái. Trong đó:
Tuyến tính phải là luật sinh có dạng: A → wB hoặc A → w;
Tuyến tính trái là luật sinh có dạng: A → Bw hoặc A → w;
(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à lớp các ngôn ngữ được sinh ra bởi văn phạm
loại 0, 1, 2, 3 tương ứng, ta có:
L3L2 L1 L0.

7


2.3. Automata hữu hạn
2.3.1 Khái niệm chung về automat
Automat: là máy tự động, là thiết bị có thể tự thực hiện công việc mà
không cần sự can thiệp của con người. Nó hoạt động dựa trên một số quy tắc và
dựa vào các quy tắc này con người lập trình cho nó hoạt động theo ý muốn của
mình. Máy tính số ngày nay chính là một máy tự động điển hình và mạnh nhất
hiện nay. Cụ thể automat 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ữ.
Finite automata (FA) là mô hình tính toán hữu hạn: có khởi đầu và kết
thúc, mọi thành phầ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.
Automata làm việc theo các bước thời gian rời rạc (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 và trước đó.
Biểu diễn một FA: Có hai cách: biểu đồ dịch chuyển và bảng dịch


()

..
)

…

δ ()

…

…..

…

δ()

..
…

..
δ(

δ ()

..
δ

…

c:= ký hiệu tiếp theo của chuỗi;
};
if (q in F) return (true);
else return (false);
c. Ví dụ
Cho automat sau:

12


Quá trình đoán nhận 00101 như sau:

d. Chú ý
Trong trường hợp FA là DFA, q là một trạng thái. Nếu FA là NFA, q là
một tập hợp.
3.1.2 Tối giản automat
a. Tư tưởng
Gom nhóm những trạng thái không thể phân biệt được thành một
nhóm(gọi là nhóm trạng thái tương đương).
Đánh dấu các trạng thái có thể phân biệt được và những trạng thái không
thể phân biệt được. Trạng thái không thể phân biệt được là những trạng thái
tương đương. Sau đó tiến hành rút gọn thông qua việc gom nhóm.
b.Giả mã
Giải thuật bắt đầu bằng việc đánh dấu các cặp trạng thái qi và qj là khác
nhau (phân biệt) nếu một trạng thái là đoán nhận còn trạng thái còn lại thì không
đoán nhận. Phần còn lại của giải thuật là xem xét một cách hệ thống các cặp
trạng thái không được đánh dấu. Khi hai trạng thái cho thấy là phân biệt, thì có
lời gọi chuỗi đệ quy DIST để thiết lập D[i,j]=1. Lời gọi DIST(i,j) không chỉ
đánh dấu qi và qj là phân biệt , nó còn đánh dấu mỗi cặp trạng thái qm,qn (với
[m,n] thuộc S[i,j]) là khác nhau cho tới lời gọi DIST(m,n).

For tất cả [m, n] € S[i, j], DIST(m,n)
End
c.Ví dụ
Cho automat đơn định sau:

Sau bước đanh dấu ta có bảng đánh dấu như sau:

Ghép các trạng thái không phân biệt được ta được DFA rút gọn:
14


3.1.3. Chuyển NFA sang DFA
a. Tư tưởng
Từ định lý nếu ngôn ngữ L là tập được chấp nhận bởi một NFA thì tồn tại
một DFA chấp nhận L. Vì vậy sẽ tồn tại một DFA tương đương NFA chấp nhận
cùng một ngôn ngữ.
b. Giả mã
Input: NFA M=(Q,∑,δ,q0,F) vào hàm dịch t của M.
OutPut: DFA tương đương
Thuật toán
1. Q’=q0
2. Repeat
2.1. If Có 1 nút X
X mà được đánh nhãn là a

Q’ và một ký tự a

với cung rời khỏi

Then

[q0,q1]

[q0,q1 [q0,q2
]
]

[q0,q2]

[q0,q1 [q0,q2
]
]

Vậy ta có DFA sau:

d. Chú ý
Cung rời từ trạng thái X xét ở trên trạng thái đích sẽ là hợp của tất cả
trạng thái bao gồm các trạng thái nằm trên đường dịch chuyển ɛ
3.1.4 Chuyển NFAɛ sang NFA
a. Tư tưởng
Từ định lý 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. Do đó, luôn tồn tại một NFA tương
đương cùng chấp nhận một ngôn ngữ với NFAɛ.
b. Giả mã
Input: NFAɛ A(Q, Σ, δ, q0, F) chấp nhận L
Output: NFA A’={Q, Σ, δ’, q0, F’}
16


Thuật toán
Tìm các thành phần của NFA như sau:

2.1. If (X

Q’ và a

)

Then
2.1.1 Trạng thái Y = δ*(q, a).
.

2.1.2. If Yϵ

Q’, then Q’ := Q’ U {Y}

2.1.3. Thêm một cung từ X vào Y nhãn là a.
Else done := true
Until done
3. Tập các trạng thái kết thúc của DM là F’ = { X
thành phân qi F}
c.Ví dụ
Cho NFAɛ:
18

Q’ | X chưá 1


Theo thuật toán trên ta tìm được các bao đóng sau:
ɛ*(q0) = {0, 1, 2, 4, 7} → q0’ = [0, 1, 2, 4, 7] = A
ɛ*(δ(A, a)) = ɛ*({3, 8}) = {1, 2, 3, 4, 6, 7, 8} → B
ɛ*(δ(A, b)) = ɛ*({5}) = {1, 2, 4, 5, 6, 7} → C

If(q)
Then RG có luật sinh:p a.
If(q0)
Then RG có luật sinh S q0 | ε.
c.Ví dụ
xét DFA cho 0(10)* sau:

Biểu diễn bởi văn phạm sau:
A 0B | 1D | 0
B 0D | 1C
C 0B | 1D | 0
D 0D | 1D
3.2.2. Chuyển văn phạm sang FA
a.Giả mã
Giải thuật xây dựng FA cho văn phạm tuyến tính phải:
Xây dựng tập Q 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.
If( A là một biến và (A) P)
Then δ([A], ε) = {[a]}
If(a là một ký hiệu kết thúc)
Then δ([a], a) = {[]}
Trạng thái bắt đầu [S], trạng thái kết thúc [ε]
21


b.Ví dụ
Xây dựng FA cho RG:

S0A ; A 10A | e


G.add(p);
}
Chú ý: Chuyển dạng tuyến tính trái thành tuyến tính phải thì ngược lại.
c. ví dụ
Cho văn phạm G = < Σ, Δ, S, P > :
P:

S S10 | 0

Ta có văn phạm tuyến tính phải G’=< Σ, Δ, S, P’ >
P’:S01S|0
3.3.2. Rút gọn văn phạm phi ngữ cảnh
a. Ý tưởng
Xuất phát từ khái niệm văn phạm rút gọn: là văn phạm 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.
1. Mọi x ∈ (Σ ∪ Δ), tồn tại chuỗi w sử dụng nó trong dẫn xuất;
2. Không có luật sinh dạng A B (với A, B ∈ Δ)
3. Nếu ngôn ngữ không chấp nhận chuỗi rỗng ε thì loại bỏ luật sinh A ε.
Để rút gọn văn phạm phi ngữ cảnh cần thực hiện 3 bước sau:
1. Loại bỏ các ký hiệu thừa
2. Loại bỏ các luật sinh ε
3. Loại bỏ các luật sinh đơn vị

23


Do đó có định lý: Cho CFG G = < Σ, Δ, S, P > với L(G) ≠ Ø, có một
CFG G = < Σ’, Δ’, S, P’ > tương đương sao cho mỗi A ϵΔ’ tồn tại w ϵ Σ* để A*
w.

Bước 2: Xây dựng P’. Với mỗi luật A →X1X2...Xn , Xi ∊ (Σ+Δ) trong P, ta
xây dựng luật sinh A → a1a2...an trong P’ với điều kiện:
Nếu Xi ∉ Ω thì ai = Xi
Nếu Xi ∊Ω thì ai = Xi | ε
Không gán đồng thời tất cả ai đều bằng ε
3. Giải thuật loại bỏ các luật sinh đơn vị
for (mỗi biến A ∊Δ) {
Tính ΔA = { B | B ∊ Δ và A →* B } ;
for (mỗi biến B ∊ΔA){
for (mỗi luật sinh B → a thuộc P){
if (B →a không là luật sinh đơn vị) {
Thêm luật sinh A → a vào P’;
}
}
}
}
c. Ví dụ
Xét văn phạm G = < Σ, Δ, S, P > :
S→A
A → aBb | ε
B → A | cB | cC
C → AC | BCD
D → ab
Áp dụng thuật toán tìm Δ’ ta có:
Δ' = {S, A, B, D}
S→A
A → aBb | ε
25