Lý thuyết automata và ngôn ngữ hình thức

Automata

Grammar

Languague

G I Ả N G V I Ê N : T S . H À C H Í T R U N G B Ộ M Ô N : K H M T K H O A C N T T , H V K T Q S Đ T : 0 1 6 8 . 5 5 8 . 2 1 . 0 2 E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M

Bài 3. Ngôn ngữ và automata hữu hạn (Formal Languagues and Finite Automata)

MỤC ĐÍCH:

 Trang bị những khái niệm về automata hữu hạn (FA);  Phân loại FA;  các phép biến đổi tương đương giữa các loại FA;  Biểu thức chính qui (RE) và sự tương đương với FA;

YÊU CẦU:

 Sinh viên nắm vững các khái niệm, các thuật toán biến đổi

và làm các dạng bài tập.

Bài 3. Ngôn ngữ và automata hữu hạn

3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε (NFAε) 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.1. Các khái niệm sơ lược

 Automata là một máy trừu tượng (mô hình tính toán) 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) - mô hình tính toán hữu hạn: có

 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;

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

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;  Hoạt động theo theo từng bước 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 đó. Nếu sử dụng bộ nhớ (memory), giả sử rằng nó có ít nhất một bộ nhớ vô hạn;

3.1. Các khái niệm sơ lược

DFA (Deterministic Finite Automata)

RE (Regular Expression)

FA (Finite Automata)

RG (Regular Grammar) or RL

NFA (Nondeterministic Finite Automata)

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.1. Các khái niệm sơ lược

 Đoán nhận ngôn ngữ: đoán nhận các từ của ngôn ngữ đó.  Hoạt động của automata bắt đầu từ một trạng thái đặc biệt,

 Giả sử rằng tại mỗi thời điểm (step, time step), automata đang ở một trạng thái nào đó (current state), đầu vào của automata đón nhận một ký tự của chuỗi cần xử lý, dưới tác động của ký tự đó automata chuyển sang một trạng thái kế tiếp (next state);

 Chuỗi được đoán nhận nếu trạng thái cuối cùng của

trang thái đầu tiên (start state);

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

automata rơi vào một trong các trạng thái kết thúc (finish states).

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.2. Automata hữu hạn đơn định (DFA)

 Định nghĩa 3.1: một DFA là một bộ năm:

A=(Q, Σ, δ, q0, F),

trong đó:

Q : tập khác rỗng, tập hữu hạn các trạng thái (p, q…); Σ : bộ chữ cái nhập vào (a, b, c …); δ : D→ Q, hàm chuyển (hay ánh xạ), D ⊆ Q × Σ, có

28/03/2012

nghĩa là δ(p, a) =q hoặc δ(p, a) = Ø, trong đó p, q  Q , a  Σ;

q0  Q : trạng thái bắt đầu (start state); F  Q : tập các trạng thái kết thúc (finish states). Trong trường hợp D = Q × Σ ta nói A là một DFA đầy đủ. Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.2. Automata hữu hạn đơn định (DFA)

 Biểu diễn automata: Cho một automata thực chất là cho hàm chuyển trạng thái của nó, có thể cho dưới dạng bảng chuyển trạng thái hoặc cho dưới dạng đồ thị chuyển.

 Định nghĩa 3.2: Đồ thị chuyển là một đa đồ thị có hướng (có thể có khuyên) G: Tập đỉnh của G được gán nhãn bởi các phần tử thuộc Q, các cung được gán nhãn bởi các phần tử thuộc Σ, nếu a ∈ Σ, p,q ∈ Q và δ(q, a) = p thì sẽ có một cung từ đỉnh q tới đỉnh p được gán nhãn a. Đỉnh vào của đồ thị chuyển ứng với trạng thái ban đầu q0.

 Định nghĩa 3.3: Bảng chuyển – bảng có kích cỡ |Q|×|Σ|, trong đó dòng i cột j của bảng là 𝛿(𝑞𝑖, 𝑎𝑗) hoặc bỏ trống.

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.2. Automata hữu hạn đơn định (DFA)

Trạng thái bắt đầu

Trạng thái kết thúc

x Phép chuyển trên nhãn x

Bảng chuyển Đồ thị chuyển

0 0 0 0

q3 q2

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.2. Automata hữu hạn đơn định (DFA)

11 0

1

0,1

111 0111 1

0 0

1 Thứ tự đọc từ trái qua phải

Automata đoán nhận chuỗi khi đọc hết xâu và rơi vào trạng thái kết thúc

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.2. Automata hữu hạn đơn định (DFA)

 Ví dụ 3.1: Cho automata A = ({q0; q1; q2}; {0, 1}, , q0, {q1}) với hàm chuyển được cho dưới dạng bảng chuyển và đồ thị chuyển như sau:

Ngôn ngữ được đoán nhận bởi automat A:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

L = {1*0*01x : x  {0, 1}*}

3.2. Automata hữu hạn đơn định (DFA)

 Ví dụ 3.2: Automat sau nhận dạng ngôn ngữ gồm chẵn các

số 1 và chẵn các số 0.

28/03/2012

 Quá trình đoán nhận các xâu: 001011, 101010, 10010 Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.2. Automata hữu hạn đơn định (DFA)

 Định nghĩa 3.4: Mở rộng của một ánh xạ δ là δ’ biến đổi

(trạng thái, chuỗi) sang trạng thái. Có nghĩa là:

 Chuỗi ω = a1a2...an được đoán nhận bởi DFA A (có nghĩa là ) nếu tồn tại một đường đi bắt đầu từ trạng thái đầu q0 và kết thúc ở trạng thái kết với dãy nhãn của đường đi là a1a2...an.

 Ngôn ngữ được chấp nhận bởi một automata A:

1. δ’(q, ) = q; 2. δ’(q, wa) = δ’(δ’(q,w), a) với  w, a.

 Các ngôn ngữ chấp nhận bởi automata hữu hạn đơn định

được gọi là ngôn ngữ chính quy.

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

L(A) = { x | δ’( q0, x )  F }

3.2. Automata hữu hạn đơn định (DFA)

 Thuật toán đoán nhận chuỗi:

q:= q0; c:= ký hiệu tiếp theo của chuỗi; while (C < > ε) do {

q:= δ(q, c); c:= ký hiệu tiếp theo của chuỗi;

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

}; if (q in F) return (true); else return (false);

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE 3.7.4. Sự tương đương giữa NFAε và RE

3.3. Automata hữu hạn đa định (NFA)

 DFA 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 là automata mà ứng với một trạng thái và một ký tự nhập, có thể có không, một hoặc nhiều phép chuyển trạng thái.

 Ví dụ 3.3: automata đa định sau nhận dạng các xâu kết

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

thúc bằng 01

3.3. Automata hữu hạn đa định (NFA)

 Xét quá trình automata A nhận dạng xâu 00101:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.3. Automata hữu hạn đa định (NFA)

 Định nghĩa 3.5: Automat hữu hạn đa định được định

nghĩa bởi bộ 5:

A = (Q, , , q0, F)

trong đó:

Q - tập hữu hạn các trạng thái.  - là tập hữu hạn các chữ cái.  - là ánh xạ chuyển trạng thái. : Q   2Q q0  Q là trạng thái khởi đầu. F  Q là tập trạng thái kết;

 Ánh xạ δ là một hàm đa trị (hàm không đơn định), vì vậy A

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

được gọi là không đơn định;

3.3. Automata hữu hạn đa định (NFA)

 Chú ý: 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 từ trạng thái q trên nhãn a.  ĐN 3.6: Hàm chuyển trạng thái mở rộng (của NFA):

1. δ(q, ) = {q} 2. δ(q, wa) = { p | r trong δ(q, w) mà pδ(r, a) }

 Ngôn ngữ L(A), với A là NFA (Q, Σ, δ, q0, F) là tập hợp : L(A) = {w | δ(q0, w) có chứa một trạng thái trong F}

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

= δ( δ(q,w), a) 3. δ(P, w) = qP δ(q, w) với P  Q

3.3. Automata hữu hạn đa định (NFA)

 Ví dụ 3.4: cho automata (hình vẽ) và xét chuỗi nhập 01001

0 0 0 1 1 q0 q0 q0 q0 q0 q0

0 1 0 0 1

q3 q1 q3 q3 q1

 Ngôn ngữ được đoán nhận bởi automata cho ở trên???

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.3. Automata hữu hạn đa định (NFA)

Ví dụ 3.5: xét chuỗi nhập w=01001 và NFA đã cho ở trên

A = ( {q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q2, q4}) Bảng chuyển Hàm chuyển mở rộng

δ

Input

Trạng thái q0 q1 q2 q3 q4

0 {q0,q3} Ø {q2} {q4} {q4}

1 {q0,q1} {q2} {q2} Ø {q4}

• δ(q0, 0) = {q0,q3} • δ(q0, 01) = δ( δ(q0, 0), 1) = δ({q0, q3},1) = δ(q0, 1)  δ(q3, 1) = {q0, q1} • δ(q0, 010) = {q0, q3} • δ(q0, 0100) = {q0, q3, q4} • δ(q0, 01001) = {q0, q1, q4}

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

Do q4  F nên w=01001  L(A)

3.3. Automata hữu hạn đa định (NFA)

 Ví dụ 3.6:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.3. Automata hữu hạn đa định (NFA)

 Ví dụ 3.7:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.3. Automata hữu hạn đa định (NFA)

 Ví dụ 3.8:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.4. NFA với dịch chuyển ε

• Ví dụ 3.9: Xây dựng automata đoán nhận chuỗi:

0*1* 2*

• Định nghĩa 3.7: NFA với -dịch chuyển (ký hiệu: NFA) là bộ năm:

A= (Q, , , q0, F),

trong đó:

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

Q: tập hữu hạn các trạng thái; : tập hữu hạn các chữ cái; : Q( {})  2Q ; q0 là trạng thái ban đầu; F Q là tập trạng thái kết thúc.

3.4. NFA với dịch chuyển ε

 Ví dụ 3.9: xây dựng NFA chấp nhận chuỗi 0*1*2*

 Cách 1: ????

0 1 2

Start 0, 1 1, 2

q0

q1

q2

 Cách 2:

0, 1, 2

0 2

Start  

 Có chăng sự tương đương giữa NFA với NFAε ???

28/03/2012

Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University

q0 q1 q2

3.4. NFA với dịch chuyển ε

0,1,...,9

,+,-

0,1,...,9



Ví dụ 3.10: tìm automata biểu diễn các số thực. 1. Có thể có một dấu + hoặc - ở đầu. 2. Sau đó là một xâu ký tự "0",..."9" 3. Dấu chấm. 4. Một xâu ký tự "0",..."9" khác.

0,1,...,9

q0 q1 q3 q5 q2

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.4. NFA với dịch chuyển ε

 Ví dụ 3.11: Automat cho ví dụ trước:

 Bảng chuyển của automata E có dạng:

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.4. NFA với dịch chuyển ε

 ĐN 3.10: Hàm chuyển trạng thái mở rộng (của NFA):

mở rộng δ thành δ* 1. δ* : Q x Σ* → 2Q 2. δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên

đường đi có thể chứa cạnh nhãn  }

 ĐN 3.11: bao đóng  ký hiệu -CLOSURE(), *) là tất

cả các trạng thái có thể chuyển tới bằng dãy {}*:

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1. *(q) = { p | có đường đi từ q tới p theo nhãn  } 2. *(P) = qP *(q)

3.4. NFA với dịch chuyển ε

 Ta có:

1. δ*(q, ) = *(q) 2. δ*(q,a) = *(δ(δ*(q, ),a)) = *(δ(*(q),a)) 3. δ*(q, wa) = *( δ( δ*(q, w), a)) hoặc

δ*(q, wa) = *(P) với P = { p | r  δ*(q, w), p  δ(r, a)}

 Ví dụ 3.12: Cho automata sau, xác định ánh xạ mở rộng

4. δ*(R, w) = qR δ*(q, w)

δ*(q0, 012)

0 1 2

Start  

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

q1 q2 q0

3.4. NFA với dịch chuyển ε

 w = 012

= *({q1}) = {q1,q2}

δ*(q0, ) = *(q0) = {q0, q1, q2} δ*(q0, 0) = * (δ(δ*(q0, ), 0)) = *(δ({q0, q1, q2}, 0)) = *(δ(q0, 0)  δ(q1, 0)  δ(q2, 0) ) = *({q0}     ) = *({q0}) = {q0, q1, q2} δ*(q0, 01) = *(δ(δ*(q0, 0), 1)) = *(δ({q0, q1, q2}, 1)) δ*(q0, 012) = *(δ(δ*(q0, 01), 2)) = *(δ({q1, q2}, 2)) = *({q2}) = {q2}

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

• Do q2  F nên w  L(A).

3.4. NFA với dịch chuyển ε

 Giải thuật đoán nhận chuỗi của NFA  Input: chuỗi nhập x$  Output: true(x được chấp nhận) hoặc false.

P = *(q0); c = nextchar; while (c <> $) {

P = * (δ(q, c)); c = nextchar;

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

} if (p  P in F)return true; else return false;

Bài 3. Ngôn ngữ và automata hữu hạn

3.1. Các khái niệm sơ lược 3.2. Automata hữu hạn đơn định (DFA) 3.3. Automata hữu hạn đa định (NFA) 3.4. Automata với dịch chuyển ε 3.5. Sự tương đương giữa DFA và NFA 3.6. Sự tương đương giữa NFAε và DFA 3.7. Biểu thức chính quy

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.5. Sự tương đương giữa DFA và NFA

 Nhận xét: Việc thiết kế các NFA dễ dạng hơn so với DFA vì không bị ràng buộc. Rõ ràng DFA chỉ là một trường hợp riêng của NFA.

 Câu hỏi: Liệu lớp ngôn ngữ nhận biết bởi NFA có rộng hơn

DFA?

 Trả lời: Với mọi ngôn ngữ L nhận biết bởi một NFA thì đều

 Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn

có một DFA nhận biết L.

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

tại một DFA chấp nhận L.

3.5. Sự tương đương giữa DFA và NFA

 Giải thuật tổng quát xây dựng DFA từ NFA:

với q0, q1, …, qi  Q;

Giả sử NFA A={Q, Σ, δ, q0, F} chấp nhận L, giải thuật xây dựng DFA A’={Q’, Σ, δ’, q0’, F’} chấp nhận L như sau: o Q’ = 2Q , phần tử trong Q’ được ký hiệu là [q0, q1, …, qi]

o q0’ = [q0]; 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 δ’([q1, q2,..., qi], a) = [p1, p2,..., pj] nếu và chỉ

nếu δ({q1, q2,..., qi }, a) = {p1, p2,..., pj}.

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

o Đổi tên các trạng thái [q0, q1, …, qi].

3.5. Sự tương đương giữa DFA và NFA

 Ví dụ 3.13: NFA A({q0, q1}, {0, 1}, δ, q0, {q1}):

NFA:

0 1

0,1

q0 q1

 Xây dựng DFA tương đương: A’ (Q’, {0, 1}, δ’, [q0], F’): o Q’ = {, [q0], [q1], [q0, q1]} o F’ = {[q1], [q0, q1]} o Hàm chuyển δ’:

DFA: 0,1

1 1

q0 q1 q2

δ’([q0], 0) = [q0, q1] δ’([q0], 1) = [q1] δ’([q1], 0) =  δ’([q1], 1) = [q0, q1] δ’([q0, q1], 0) = [q0, q1] δ’([q0, q1], 1) = [q0, q1]

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.5. Sự tương đương giữa DFA và NFA

 Ví dụ 3.13: Tìm DFA tương đương cho NFA trong ví dụ 3.3.

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.5. Sự tương đương giữa DFA và NFA

NFA: 0,1 DFA (đổi tên các nhãn):

1 0 1 0 q0 q1 q2

DFA: 1

1 0

[q0] [q0, q1] [q0, q2]

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.6. Sự tương đương giữa NFA và DFA

 Định lý 2: 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.

 Thuật toán: Giả sử ta có NFA A(Q, Σ, δ, q0, F) chấp nhận

L, ta xây dựng: NFA A’={Q, Σ, δ’, q0, F’} như sau: 1. F’ = F  q0 nếu *( q0) chứa ít nhất một trạng thái

thuộc F. Ngược lại, F’ = F;

 Hệ quả: Nếu L là tập được chấp nhận bởi một NFA thì tồn

2. δ’(q, a) = δ*(q, a).

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

tại một DFA chấp nhận L.

3.6. Sự tương đương giữa NFA và DFA

 Giải thuật xây dựng δ’ cho DFA tương đương:

Tìm kiếm T = * (q0) ; T chưa được đánh dấu; Thêm T vào tập Q’ (of DFA); while (xét trạng thái T  Q’ chưa đánh dấu){

Đánh dấu T; forearch (với mỗi ký hiệu nhập a){

U:= *((T,a)); if(U không thuộc tập trạng thái Q’){

add U to Q’; Trạng thái U chưa được đánh dấu;

} [T,a]= U;

}

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.6. Sự tương đương giữa NFA và DFA

Start



 Ví dụ 3.14: Xây dựng NFA tương đương.

q0

q2

q1

Start

0, 1

1, 2

q0

q2

q1

 M’ = {Q, Σ, δ’, q0, F’} o Q = {q0, q1, q2} o Σ = {0, 1, 2}

0, 1, 2

Inputs

δ’

0 {q0, q1, q2} 



1 {q1, q2} {q1, q2} 

Trạng thái q0 q1 q2

2 {q2} {q2} {q2}

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

o Trạng thái bắt đầu: q0 o F’ = {q0, q2} o Hàm chuyển δ’

3.6. Sự tương đương giữa NFA và DFA

 Ví dụ 3.15: xây dựng DFA tương đương cho NFA sau:

0,1,...,9

,+,-

0,1,...,9



0,1,...,9

q0 q1 q3 q5 q2

q4

28/03/2012

3.6. Sự tương đương giữa NFA và DFA

 DFA tương đương:

0,1,...,9

+,-

[q0, q1]

[q1]

[q1,q4]

[q2,q3,q5]

0,1,...,9

[q3,q5]

0,1,...,9

28/03/2012

[q2]

3.6. Sự tương đương giữa NFA và DFA

 Ví dụ 3.16: xây dựng DFA tương đương với NFA sau: A = (Q={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Σ={a, b}, δ, 0, F={10})



2 3

    a b b 10 0 1 6 8 7 9



4 5

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University



3.6. Sự tương đương giữa NFA và DFA

● *(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 ● *(δ(B, a)) = *({3, 8}) → B ● *(δ(B, b)) = *({5, 9}) = {1, 2, 4, 5, 6, 7, 9} → D ● *(δ(C, a)) = *({3, 8}) → B ● *(δ(C, b)) = *({5}) = → C ● *(δ(D, a)) = *({3, 8}) → B ● * (δ(D, b)) = *({5,10}) = {1, 2, 4, 5, 6, 7, 10} → E ● *(δ(E, a)) = *({3, 8}) → B ● *(δ(E, b)) = *({5}) = → C

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.6. Sự tương đương giữa NFA và DFA

• Ký hiệu bắt đầu: q0’ = A (↔ *(q0) ) • Tập trạng thái kết thúc: F’ = {E} (vì trong E có chứa trạng

thái 10  F)

Ký hiệu nhập

Trạng thái

C a b

a b A B D E b

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.7.1. Khái niệm về biểu thức chính quy

 Định nghĩa: Biểu thức chính quy được định nghĩa một

cách đệ quy như sau: 1.  là biểu thức chính quy. L()={}.  là biểu thức chính quy. L()={}. nếu a, a là biểu thức chính quy. L(a)={a}. 2. Nếu r, s là các biểu thức chính quy thì:

 ((r)) là biểu thức chính quy. L((r))=L(r);  r+s là biểu thức chính quy. L(r+s)=L(r)L(s);  r.s là biểu thức chính quy. L(r.s)=L(r).L(s);  r* là biểu thức chính quy. L(r*)=L(r)*.

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

3. Biểu thức chính quy chỉ định nghĩa như trong 1 và 2.

3.7.1. Khái niệm về biểu thức chính quy

 Ví dụ 3.17: biểu thức chính quy: L(00)={00} L((0+1)*) = {0,1}* L((0+1)*011) = {0,1}*011

 00 :  (0+1)* :  (0+1)*011 :  (0+1)*00(0+1)*:L((0+1)*00(0+1)*) = {0,1}*00 {0,1}*  (0+ )(1+10)* : tất cả các chuỗi không có hai số 0 liên

{, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... }

 0*1*2* :  00*11*22* = 0+1+2+

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

tiếp = {, 0, 01, 010, 1, 10, 01010, 0111, ... }

3.5.1. Khái niệm về biểu thức chính quy

Tính chất đại số của biểu thức chính quy:

• r +  =  + r = r • r + r = r • r + s = s + r • (r + s) + t = r + (s + t) = r + s + t

• * =  • * =  • r*r* = r* • (r*)* = r* • r* =  + r + r2 + … + rk + … • r* =  + r+ • ( + r)+ = ( + r)* = r* • r*r = r r* = r+

28/03/2012

Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Phép hợp: Phép bao đóng:

3.7.1. Khái niệm về biểu thức chính quy

Tính chất đại số của biểu thức chính quy:

Phép nối kết: Tổng hợp:

• (r* + s*)* = (r*s*)* = (r + s)* • (rs)*r = r(sr)* • (r*s)* r* = (r + s)*

• r = r = r • r = r =  • (r + s) t = rt + st • r (s + t) = rs + rt

28/03/2012

Thứ tự ưu tiên của phép toán: * (bao đóng), . (phép nối kết), + (phép hợp).

3.7.1. Khái niệm về biểu thức chính quy

 Ví dụ 3.18: Biểu thức chính quy cho ngôn ngữ gồm các xâu

nhị phân mà không có hai số 0 hay hai số 1 liên nhau.

(01)*+(10)*+0(10)*+1(01)*

(+1)(01)*(+0)

hoặc là:

 Bài tập: Viết biểu thức chính quy cho ngôn ngữ gồm các

Thứ tự ưu tiên của phép toán: *, . , + Do đó: 01* + 1 được hiểu như sau: (0(1)*) + 1

28/03/2012

xâu 0, 1 trong đó bắt đầu bằng số 1, kết thúc bằng chuỗi 01.

Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.7.2. Sự tương đương giữa FA và RE

 Sự tương đương giữa DFA, NFA, và ε-NFA đã được thiết lập. Để chứng minh chúng tương đương với biểu thức chính quy (REGEX) ta chỉ cần chứng minh:

1. Với mọi DFA D, có một REGEX R sao cho L(R)=L(D). 2. Với mọi RE R có NFAε A sao cho L(A)=L(R).

NFA

DFA

Định lý 1

Định lý 4 Định lý 2

28/03/2012

NFA RE Định lý 3

3.7.2. Sự tương đương giữa FA và RE

 Định lý 3: nếu r là RE thì tồn tại một NFA chấp nhận L(r).  Chứng minh: quy nạp theo số phép toán 1. Xét trường hợp r không có phép toán nào:

Start

r = a

r = 

r = 

2. Xét r có i phép toán: r = r1 + r2, r = r1r2 hoặc r = r1* Trước hết ta xây dựng các NFA:

28/03/2012

A1 = (Q1, Σ1, δ1, q1, {f1}) và A2 = (Q2, Σ2, δ2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2)

3.7.2. Sự tương đương giữa FA và RE

Xây dựng NFA A thỏa mãn các RE như sau:



Start



Start



r = r1 + r2



Start



r = r1r2



28/03/2012

r = r1*

3.7.2. Sự tương đương giữa FA và RE

Start

Ví dụ 3.19: xây dựng NFA chấp nhận RE r = 01* + 1 • r có dạng: r = r1 + r2 với r1 = 01* và r2 = 1 • r1 có dạng r1 = r3r4 với r3 = 0 và r4 = 1* • r4 có dạng r4 = r5* với r5 = 1

r2



Start

Start q7

r5 

0 r3



r4 = r5* = 1*

28/03/2012

3.7.2. Sự tương đương giữa FA và RE



r1 = r3r4 = 01*



Start



Start



q10



28/03/2012

r = r1 + r2 = 01* + 1

3.7.2. Sự tương đương giữa FA và RE

 Ví dụ: Tìm NFA tương đương cho (0+1)*1(0+1)

r=(0+1)*

 1   1   r=(0+1)  

0  

  

 1 1    

r=(0+1)*1(0+1) 1

   

0 0    

28/03/2012



Bài 3. Ngôn ngữ và automata hữu hạn

28/03/2012

3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và RE

3.7.3. Sự tương đương giữa DFA và RE

 Định lý 4: Nếu L được chấp nhận bởi một DFA, thì L được

 Chứng minh:

 L được chấp nhận bởi DFA A({q1, q2,..., qn}, Σ, δ, q1, F)  Đặt Rk

ký hiệu bởi một RE.

ij = {x | δ(qi, x) = qj và nếu δ(qi, y) = ql (y  x) thì l ≤ k} (có nghĩa là Rk ij - tập hợp tất cả các chuỗi làm cho automata đi từ trạng thái i đến trạng thái j mà không đi ngang qua trạng thái nào lớn hơn k)

Rk

 Định nghĩa đệ quy của Rk ij = Rk-1

ik(Rk-1

kj  Rk-1

R0

ij =

ij: kk)*Rk-1 ij {a | δ(qi, a) = qj}, nếu i ≠ j {a | δ(qi, a) = qj}  {}, nếu i = j

28/03/2012

3.7.3. Sự tương đương giữa DFA và RE

● Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rk

ij

ij . ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc 

lm sao cho L(Rk-1

kj) + rk-1 ij

đều tồn tại một biểu thức chính quy ký hiệu cho Rk  k = 0: R0  Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại RE lm) = rk-1 Rk-1  Vậy đối với rk ij ta có thể chọn RE: kk)*(rk-1 ik)(rk-1 ij = (rk-1 rk → bổ đề đã được chứng minh

𝑞𝑗∈𝐹

RE:

1j1 + rn

1j2 + … + rn

1jp

. Vậy L có thể được ký hiệu bằng ● nhận xét: 𝐿 𝐴 = Rn 1j

28/03/2012

r = rn với F = {qj1, qj2, …, qjp}

3.7.3. Sự tương đương giữa DFA và RE

 Ví dụ 3.20: viết RE cho DFA sau: 1

1 Start 0

q1 q2 q3

 Ta cần viết biểu thức:

r = r3

12 + r3

 Ta có:

12 = r2

13(r2

33)*r2

32 + r2

13 = r2

13(r2

33)*r2

33 + r2

28/03/2012

0 0, 1

3.7.3. Sự tương đương giữa DFA và RE

k = 0

k = 1

k = 2

(00)*



11

0(00)*

12

0*1

13

0(00)*

21

(00)*

 + 00



22

1 + 01

0*1

23

(0 + 1)(00)*0



31

0 + 1

(0 + 1)(00)*

0 + 1

32 rk rk rk rk rk rk rk rk rk

 + (0 + 1)0*1



33

 Thay vào và rút gọn, ta có:

28/03/2012

r = 0*1((0 + 1)0*1)* ( + (0 + 1)(00)*) + 0(00)*

Lý thuyết automata và ngôn ngữ hình thức - Bài 3