
Tin học lý thuyết - Chương 3
Mô tả tài liệu
ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Nội dung chính: Trong chương này, ta sẽ nghiên cứu một loại "máy trừu tượng" gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết, hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ đề cập đến biểu thức chính quy - một phương tiện khác để xác định...
Tóm tắt nội dung
quan hệ giữa cơ chế ôtômát và các biểu thức chính quy dùng ký hiệu cho ngôn ngữ.
Vẽ sơ đồ chuyển trạng thái (đơn định hoặc không đơn định) từ một biểu
Ôtômát hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các input
Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn
hạn, và lý thuyết về ôtômát hữu hạn là một công cụ thiết kế hữu ích cho các hệ thống
Mỗi trạng thái của một mạng chuyển mạch với n cổng bất kỳ sẽ là một
phải nhớ một số hữu hạn thông tin như các ký tự bắt đầu hình thành những chuỗi từ
Máy tính cũng có thể được xem như một hệ thống trạng thái hữu hạn.
bất kỳ là một trong những số rất lớn và hữu hạn của số trạng thái.
cũng là một hệ thống trạng thái hữu hạn, vì số các tế bào thần kinh hay gọi là neurons
Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự
Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -gồm một tập hữu hạn các trạng
thái và một tập các phép chuyển từ trạng thái này tới trạng thái khác trên các ký hiệu
đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó).
thái, thường ký hiệu là q0, gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu).
trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận.
DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường
chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a chuyển từ
tồn tại dãy các phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái bắt
Chẳng hạn, sơ đồ chuyển của một DFA được mô tả trong hình 3.1.
cũng là q0 trong trường hợp này, được chỉ ra bằng hai vòng tròn.
Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm thành phần (Q, Σ, δ,
. Q là tập hợp hữu hạn các trạng thái.
. δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái được
cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a.
. F ⊆ Q là tập các trạng thái kết thúc.
Ta vẽ DFA như là bộ điều khiển hữu hạn, với mỗi trạng thái thuộc Q, DFA đọc một
Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển
sang trạng thái được xác định bởi hàm chuyển δ(q, a), rồi dịch đầu đọc sang phải một
Nếu δ(q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận
Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta mở rộng
hàm chuyển δ để áp dụng đối với một trạng thái trên chuỗi hơn là một trạng thái trên
Ta định nghĩa hàm chuyển δ như một ánh xạ từ Q × Σ* → Q với ý
nghĩa δ(q, w) là trạng thái DFA chuyển đến từ trạng thái q trên chuỗi w.
- Q là tập các trạng thái.
Ký hiệu q và p (có hoặc không có chỉ số) là các
- w, x, y và z (có hoặc không có chỉ số) là các chuỗi ký hiệu nhập.
Một chuỗi w được chấp nhập bởi ôtômát hữu hạn M (Q, Σ, δ, q0, F) nếu δ(q0, w) = p
Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp:
table) để mô tả các phép chuyển trạng thái của một ôtômát hữu hạn.
chuyển, hàng chứa các trạng thái thuộc tập trạng thái của ôtômát và cột là các ký hiệu
Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát
trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu
phép chuyển từ một trạng thái trên cùng một ký hiệu nhập.
chuỗi các phép chuyển, tương ứng với chuỗi nhập, từ trạng thái bắt đầu đến trạng thái
có chuỗi phép chuyển qua các trạng thái q0, q0, q0, q3, q4, q4 có nhãn tương ứng là 0,
Chú ý rằng có thể xem ôtômát hữu hạn đơn định - DFA (hay gọi tắt là FA) là một
trường hợp đặc biệt của NFA, trong đó mỗi trạng thái chỉ có duy nhất một phép
Vì thế trong DFA, với một chuỗi nhập w và trạng thái
Khi có sự lựa chọn trạng thái kế tiếp, chẳng hạn như từ trạng thái q0 trên ký
Mỗi trạng thái kế tiếp mà ôtômát có thể chuyển đến sẽ tương ứng với
Một cách hình thức ta định nghĩa ôtômát hữu hạn không đơn định NFA là một bộ 5
thành phần (Q, Σ, δ, q0, F) trong đó Q, Σ, q0 và F có ý nghĩa như trong DFA, nhưng δ
Khái niệm δ(q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển trên nhãn
2. δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p thuộc δ(r, a)}
Ngôn ngữ L(M), với M là ôtômát hữu hạn không đơn định NFA (Q, Σ, δ, q0, F) là tập
L(M) = {w | δ(q0, w) có chứa một trạng thái trong F }
Vì mỗi DFA là một NFA, nên rõ ràng lớp ngôn ngữ được chấp nhận bởi NFA cũng
bao gồm các tập chính quy (đây chính là ngôn ngữ được chấp nhận bởi DFA ).
đó cho thấy DFA có thể mô phỏng được hoạt động của NFA, nghĩa là với mỗi NFA,
ta có thể xây dựng một DFA tương đương (chấp nhận cùng một ngôn ngữ với nó).
Đặt một DFA mô phỏng hoạt động của NFA là cho phép các trạng thái của DFA
tương ứng với tập các trạng thái của NFA.
điều khiển tất cả các trạng thái mà NFA có thể chuyển đến khi đọc cùng một input
ĐỊNH LÝ 3.1 : Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA
Đặt M (Q, Σ, δ, q0, F) là NFA chấp nhận L.
- Các trạng thái của M’ là tất cả các tập hợp con của tập trạng thái của M, hay
Một phần tử trong Q’ được ký hiệu là [q1, q2,..., qi], trong đó các trạng
Ta xem [q1, q2,..., qi] là một trạng thái đơn của DFA tương ứng
với một tập trạng thái của NFA.
- 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
Với ⏐x⏐= 0 , ta có x = ε và q0’ = [q0] nên (1) hiển nhiên đúng
Dễ thấy rằng δ’(q0’, x) ∈ F' khi và chỉ khi δ(q0, x) có chứa ít nhất một trạng thái ∈ F.
Vì NFA và DFA chấp nhận cùng các tập hợp, nên ta sẽ không phân biệt chúng trừ khi
Thí dụ 3.5 : Cho NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển δ như sau :
Ta xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) chấp nhận L(M) như sau :
Thực tế, có rất nhiều trạng thái của NFA không có hàm chuyển đến từ trạng thái bắt
đầu từ trạng thái [q0] và thêm vào các trạng thái mới cho DFA chỉ khi có các hàm
Bạn có nhận xét gì về kích thước giữa một DFA và một NFA tương đương với nó
Ta mở rộng mô hình NFA cho phép các phép chuyển trên nhãn rỗng ε.
sau đây của một NFA chấp nhận chuỗi gồm một số bất kỳ (có thể là 0) chữ số 0 sau
nói NFA chấp nhận một chuỗi w nếu có đường truyền nhãn w từ trạng thái bắt đầu
Định nghĩa: Một cách hình thức ta định nghĩa NFA với ε-dịch chuyển là bộ 5 thành
phần (Q, Σ, δ, q0, F) với tất cả các thành phần có ý nghĩa như trên, nhưng hàm chuyển
Khái niệm δ(q, a) gồm tất cả các trạng thái p sao cho có phép chuyển nhãn a từ q tới
p, trong đó a là một ký hiệu thuộc Σ hoặc là ε.
δ*(q,w) chứa tất cả các trạng thái p sao cho có thể đi từ q tới p
Ta sử dụng ε-CLOSURE(q) để xác định tập tất cả các đỉnh p sao cho có đường đi từ q
Vì đường đi chỉ có một đỉnh q0 (không có cung trên đường đi) là đường đi từ q0 tới q0
Đặt ε-CLOSURE(P) = ∪q∈P ε-CLOSURE(q), trong đó P là một tập các trạng thái và
q là một trạng thái.
trong đó tập P = {p | có r trong δ*(q, w) sao cho p ∈ δ(r, a)}, ∀w ∈ Σ* và a ∈ Σ
Ta mở rộng δ và δ* trên tập hợp các trạng thái R như sau :
Nhận xét : δ*(q, a) và δ(q, a) không nhất thiết bằng nhau vì δ*(q, a) gồm tất cả các
trạng thái có thể chuyển đến được từ q trên nhãn a gồm cả đường đi nhãn ε, trong khi
đó δ(q, a) chỉ gồm các trạng thái có thể đến được từ q chỉ bằng các cung nhãn a.
Tương tự δ*(q, ε) có thể cũng không bằng δ(q, ε).
Ta định nghĩa L(M), ngôn ngữ được chấp nhận bởi NFAε M = (Q, Σ, δ, q0, F) là tập
L(M) = {w | δ*(q0, w) có chứa ít nhất một trạng thái trong F}
Theo khái niệm hình thức, ta có NFA M ({q0, q1, q2}, {0, 1, 2}, δ, q0, {q2}) với hàm
Do δ*(q0, 012) có chứa trạng thái q2 ∈ F nên chuỗi w ∈ L(M).
Tương tự như NFA, khả năng có thể thực hiện phép chuyển trên nhãn ε của NFAε
cũng không làm cho NFAε chấp nhận được các tập hợp không chính quy.
ĐỊNH LÝ 3.2 : Nếu L được chấp nhận bởi một NFA có ε-dịch chuyển thì L cũng
được chấp nhận bởi một NFA không có ε-dịch chuyển.
Đặt M (Q, Σ, δ, q0, F) là NFA với ε-dịch chuyển.
Ta xây dựng NFA M’(Q, Σ, δ’, q0, F’) tương đương không có ε-dịch chuyển,
F ∪ {q0} nếu ε-CLOSURE(q0) chứa một trạng thái thuộc F
có thể không đúng với x = ε vì δ’(q0, ε) = {q0} trong khi δ *(q0, ε) = ε-CLOSURE(q0).
Với | x | = 1 thì x là một ký hiệu a và δ’(q, a) = δ *(q, a) theo định nghĩa δ’.
Để đầy đủ chứng minh ta còn phải chỉ ra rằng δ’(q0, x) chứa một trạng thái
trong F’ nếu và chỉ nếu δ *(q0, x) chứa một trạng thái trong F.
Nếu δ *(q0, x) chứa một trạng thái trong F thì chắc chắn δ’(q0, x) chứa cùng
Ngược lại, nếu δ’(q0, x) chứa một trạng thái trong F’ khác hơn q0
thì δ(q0, x) phải chứa một trạng thái trong F (vì tập F và F’ chỉ chênh lệch nhau
Nếu δ’(q0, x) có chứa trạng thái q0 và q0 cũng là một trạng thái thuộc
tập trạng thái kết thúc F thì vì δ *(q0, x) = ε-CLOSURE(δ(δ *(q0, w),a)), nên trạng
thái chung trong ε-CLOSURE(q0) và trong F phải ở trong δ *(q0, x).
Ta xây dựng NFA tương đương M’(Q, Σ, δ’, q0, F’) chấp nhận L(M) với các thành
- Với mỗi trạng thái q và ký hiệu nhập a, chỉ có duy nhất một đường truyền
Giả sử mỗi trạng thái của DFA là một tập trạng thái của NFA, DFA dùng trạng thái
của mình để lưu giữ tất cả các trạng thái của NFA đạt được sau khi NFA đọc một ký
con của các trạng thái thuộc NFA, đạt được khi NFA đi từ trạng thái bắt đầu theo một
Các trạng thái thực sự được dùng trong sơ đồ chuyển cho một DFA sẽ
được xác định theo các phép chuyển trạng thái trên nhãn là mọi ký hiệu từ trạng thái
bắt đẩu của DFA, và sau đó lần lượt được bổ sung thêm vào tập trạng thái nếu như nó
Ta dùng các tác vụ sau để lưu giữ các tập trạng thái của NFA :
(q : là một trạng thái của NFA, T : là tập trạng thái của NFA)
a) ε-closure(q) : là tập trạng thái của NFA đạt được từ trạng thái q trên sự
b) ε-closure(T) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q
c) δ(T, a) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc
Trước khi đọc vào một ký tự nhập, DFA có thể ở một trạng thái bất kỳ trong
các trạng thái thuộc ε-closure(q0) với q0 là trạng thái bắt đầu của NFA.
Giả sử các trạng thái của T là các trạng thái đạt được từ q0 trên các ký hiệu
Khi đọc a, NFA có thể chuyển đến một trạng
thể ở bất kỳ trạng thái nào trong ε-closure(δ(T, a)) sau khi đã đọc a.
Trạng thái bắt đầu ε-closure(q0) chỉ là một trạng thái trong các trạng thái
While Có một trạng thái T của DFA chưa được đánh dấu do
If U không có trong tập trạng thái của DFA then
Ta xây dựng các trạng thái và bảng hàm chuyển cho DFA theo cách như sau :
có thể chuyển đến sau khi đọc một chuỗi ký hiệu nhập gồm: tất cả sự truyền rỗng có
- Trạng thái bắt đầu của DFA là ε-closure(q0)
- Các trạng thái và hàm chuyển sẽ được thêm vào D bằng giải thuật trên.
- Một trạng thái của DFA là trạng thái kết thúc nếu nó là tập các trạng thái của
Việc tính toán ε-closure(T) có thể xem như quá trình tìm kiếm một đồ thị của các nút
từ các nút cho trước và đồ thị bao gồm toàn những cạnh có nhãn ε của NFA.
thuật đơn giản để tìm ε-closure(T) là dùng Stack để lưu giữ các trạng thái mà cạnh
Từ các tập trạng thái này, ta xác định được A là trạng thái bắt đầu, E là trạng thái kết
thúc (vì trong E có chứa trạng thái 10 là trạng thái kết thúc của NFA) và bảng hàm
Từ bảng hàm chuyển như trên, ta xây dựng sơ đồ chuyển trạng thái cho DFA tương
được duy nhất từ một chuỗi nhập bất kỳ và trạng thái bắt đầu.
Lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn cũng có thể được mô tả thông
Kleene trên các tập hợp chuỗi để định nghĩa biểu thức chính quy và chứng tỏ rằng lớp
ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn thì thực sự là lớp ngôn ngữ được
Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả
1) ∅ là biểu thức chính quy ký hiệu cho tập rỗng
2) ε là biểu thức chính quy ký hiệu cho tập {ε}
3) ∀a ∈ Σ, a là biểu thức chính quy ký hiệu cho tập {a}
4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s),
(rs) và ( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R ∪ S, RS, R* tương
Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng
Như trên ta nói, biểu thức chính quy dùng ký hiệu cho một lớp ngôn ngữ.
hãy thử liệt kê một vài chuỗi và hình dung lớp ngôn ngữ được ký hiệu bởi biểu
Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho
ngôn ngữ được ký hiệu bởi biểu thức chính quy r; ngược lại một cách tổng quát, ta có
Thí dụ 3.11 : Một số biểu thức chính quy ký hiệu cho các ngôn ngữ :
. (0+1)*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0
. (1+10)* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số
. (0+ε)(1+10)* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp.
. 0*1*2* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một
. 00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0*1*2* với ít nhất một trong
Thí dụ 3.12 : Biểu thức chính quy ký hiệu cho tập hợp các chuỗi tên biến đúng trong
Pascal nếu như nó bắt đầu bằng ít nhất một chữ cái và theo sau đó là các chữ cái, số,
Thí dụ 3.13 : Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ
âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sau đó là một chuỗi
các ký hiệu số với ít nhất là một số.
Nhận xét : Thông thường, việc tìm một biểu thức chính quy ký hiệu cho một ngôn
ngữ khó hơn việc xác định ngôn ngữ được ký hiệu bởi một biểu thức chính quy vì
Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng
Như trên đã nói, các ngôn ngữ được chấp nhận bởi ôtômát hữu hạn cũng là các ngôn
gọi ngôn ngữ chấp nhận bởi ôtômát hữu hạn là các tập chính quy.
trong) biểu thức chính quy rằng có tồn tại một NFA với ε-dịch chuyển chấp nhận
cùng ngôn ngữ; đồng thời với mỗi DFA cũng có một biểu thức chính quy xác định
ĐỊNH LÝ 3.3: Nếu r là biểu thức chính quy thì tồn tại một NFA với ε-dịch
Ta sẽ chứng minh quy nạp theo số phép toán của biểu thức chính quy r rằng có tồn tại
một NFA M với ε-dịch chuyển có một trạng thái kết thúc và không có các phép
chuyển khỏi trạng thái này chấp nhận biểu thức chính quy r: L(M) = L(r).
Cả hai biểu thức chính quy r1, r2 có ít hơn i phép toán, vậy ta có 2 ôtômát hữu hạn
Vì các trạng thái có thể thay đổi tên nên ta giả sử hai tập trạng thái Q1
Đặt q0 là trạng thái bắt đầu mới và {f0} là tập trạng thái kết thúc
mới, ta xây dựng NFA M (Q1 ∪ Q2 ∪ {q0, f0}, Σ1 ∪ Σ2, δ, q0, {f0}), trong đó δ được xác
Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f1, f2 trong M1,
Vì vậy tất cả các phép chuyển của M1 và M2 đều có trong M.
và chỉ khi có đường đi nhãn x trong M1 từ q1 đến f1 hoặc có đường đi nhãn x trong M2
Đặt M1 và M2 là các ôtômát NFA như trong trường hợp trên và ta xây dựng ôtômát M
(Q, Σ , δ, {q1}, {f2}), trong đó δ được xác định như sau:
có nhãn x từ q1 tới f1 sau đó là một cung từ f1 tới q2 nhãn ε và tiếp đến là đường đi từ
Xây dựng M (Q1∪ {q0, f0} Σ1, δ, q0, {f0}), trong đó δ được cho:
đường đi từ q0 tới f0 bằng nhãn ε; hoặc đường đi từ q0 tới q1 bằng nhãn ε và sau đó là
đi từ q0 tới f0 nhãn là x nếu và chỉ nếu ta có thể viết x = x1 x2 ...
đơn 0, 1 và các chuỗi bit nhị phân bắt đầu bằng bit 0, theo sau là một chuỗi bit 1 với
Ta sẽ lần lượt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào
của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng
Bây giờ, ta cần chứng tỏ rằng mọi tập hợp được chấp nhận bởi một ôtômát hữu hạn
thì cũng được ký hiệu bởi một số biểu thức chính quy.
Đặt L là tập hợp được chấp nhận bởi DFA M ({q1, q2,..., qn}, Σ, δ, q1, F).
Đặt Rkij là tập hợp tất cả các chuỗi x sao cho δ(qi, x) = qj và nếu δ(qi, y) = ql, với y là
(Chú ý, khái niệm "đi ngang qua một trạng thái" có nghĩa là có phép
chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k).
trạng thái nên Rnij sẽ là tập hợp tất cả các chuỗi làm ôtômát đi từ qi tới qj.
Một cách hình thức, Rkij định nghĩa như trên là các chuỗi nhập hay nguyên nhân đưa
M từ qi tới qj không đi ngang qua trạng thái cao hơn qk, nghĩa là xảy ra hoặc một
mà không ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là
Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy rkij ký hiệu cho ngôn
. k = 0 : khi đó R0ij là tập hợp hữu hạn các chuỗi có một ký hiệu hoặc ε.
Trong đó {a1, a2,..., ap} là tập hợp tất cả các ký hiệu a sao cho δ(qi, a) = qj.
Cuối cùng ta có nhận xét rằng L(M) = ∪qj ∈ F Rn1j vì Rn1j ký hiệu cho tất cả các nhãn
Thí dụ 3.15 : Viết biểu thức chính quy ký hiệu cho ngôn ngữ được chấp nhận bởi
Gọi DFA được chỉ ra trong hình 3.10 là M ({q1, q2, q3}, {0, 1}, δ, q1, {q2, q3}).
thấy, tập hợp tất cả các chuỗi được chấp nhận bởi DFA trên là các chuỗi làm cho
ôtômát chuyển từ trạng thái bắt đầu q1 đến một trong hai trạng thái kết thúc q2 và q3
và không chuyển qua số tối đa là 3 (k = 3) trạng thái của ôtômát.
thức chính quy ký hiệu cho tập hợp này như sau :
Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị rkij
với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ ra trong bảng
Các ký hiệu từ vựng (token) trong một ngôn ngữ lập trình thì hầu hết không có sự
Một ví dụ khác, các định danh của FORTRAN có độ dài giới hạn là 6 và các chữ cái
chính quy mô tả các ký hiệu từ vựng và phát sinh một ôtômát hữu hạn đơn giản nhận
thành một NFA với ε-dịch chuyển và sau đó xây dựng tập hợp con các trạng thái để
có thể phát sinh DFA một cách trực tiếp hơn là tìm cách loại bỏ các phép chuyển
thế một chuỗi bởi mọi chuỗi kết hợp với một biểu thức chính quy cho trước.
cho phép thay thế các chuỗi có dạng bbb* thành chuỗi có một ký tự b.
sẽ cho phép xóa đi tất cả các file với tên tập tin bắt đầu bằng tmp, sau đó là một chuỗi
Ta có thể chuyển một biểu thức chính quy r sang DFA chấp nhận mọi r.
sự hiện diện của ký hiệu * sẽ cho phép ta nhận dạng một thành phần của L(r) bắt đầu
cách duyệt qua chúng một lần, tuy DFA có thể có số trạng thái là hàm mũ của độ dài
chuyển thành một NFA có ε-dịch chuyển và sau đó NFA này được mô phỏng một
Mô tả ngôn ngữ được chấp nhận bởi các ôtômát hữu hạn với sơ đồ chuyển được
Xây dựng các sơ đồ chuyển ôtômát hữu hạn chấp nhận các ngôn ngữ sau trên bộ
a) Tập các chuỗi trên {0, 1} có chứa một số chẵn các số 0 và một số lẻ các số 1
Tìm NFA không có ε-dịch chuyển nhận dạng cùng ngôn ngữ với các NFA sau :
Viết biểu thức chính quy và vẽ NFA đoán nhận các ngôn ngữ sau :
a) Tập hợp các chuỗi trên Σ = {1, 2, 3} sao cho ký hiệu cuối cùng đã có xuất
b) Tập hợp các chuỗi trên Σ = {0, 1} trong đó có một cặp ký tự 0 cách nhau
Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ :
Vẽ NFA với ε-dịch chuyển được cho bởi các biểu thức chính qui sau.
Hãy tìm các biểu thức chính qui tương ứng với các sơ đồ chuyển trạng thái sau:
Viết chương trình cho ra một FA tương ứng khi đầu vào là một biểu thức chính