Bài giảng Lý thuyết automat và ứng dụng: Chương 5, 6, 7

Chương 5:

Automata xuống Automata đẩyđẩy xuống utomata) own AAutomata) ((PPush ush DDown

Nội dung:

• Khái niệm về PDA

• PDA đơn định và không đơn định

• PDA chấp nhận chuỗi bằng Stack rỗng và PDA chấp

nhận chuỗi bằng trạng thái kết thúc

• Sự tương đương giữa PDA và CFL

PDAPDA

07/11/2011

(cid:1) Ngôn ngữ chính qui: – Văn Phạm chính qui – Automat hữu hạn (NFA, DFA)

– CFG – PDA

(cid:1) Ngôn ngữ phi ngữ cảnh:

(cid:1) Chỉ có nondeterministic PDA định nghĩa được tất cả CFL. (cid:1) Deterministic PDA chỉ đoán nhận được tập con, tuy nhiên cũng bao gồm phần lớn các ngôn ngữ lập trình.

PDAPDA

Ví dụ: xét L = {wcwR | w ∈∈∈∈ (0 + 1)*} được sinh ra từ CFG

S → 0S0 | 1S1 | c

Ta xây dựng PDA như sau:

• Bộ điều khiển có 2 trạng thái q1 và q2 • Stack có 3 ký hiệu: xanh (B), vàng (Y) và đỏ (R) • Quy tắc thao tác trên automata:

PDAPDA

Các khái niệm:

• Phân loại PDA: đơn định (DPDA) và không đơn định (NPDA) • Phép chuyển: có 2 kiểu

絃 Phụ thuộc ký hiệu nhập: với một trạng thái, một ký hiệu tại đỉnh Stack và một ký hiệu nhập, PDA lựa chọn trạng thái kế tiếp, thay thế ký hiệu trên Stack và di chuyển đầu đọc trên băng nhập. 絃 Không phụ thuộc ký hiệu nhập (ε – dịch chuyển): ký hiệu nhập không được dùng, đầu đọc không di chuyển.

• Ngôn ngữ được chấp nhận bởi PDA

絃 Bởi Stack rỗng 絃 Bởi trạng thái kết thúc

Một ngôn ngữ được chấp nhận bởi PDA khi và chỉ khi nó là một ngôn ngữ phi ngữ cảnh.

07/11/2011

PDAPDA

Định nghĩa: một PDA M là một hệ thống 7 thành phần

M (Q, Σ, Γ, δ, q0, Z0, F)

• Q : tập hữu hạn các trạng thái • Σ : bộ chữ cái nhập • Γ : bộ chữ cái Stack • δ : hàm chuyển Q x (Σ ∪ {ε}) x Γ → tập con của Q x Γ* • q0 : trạng thái khởi đầu • Z0 : ký hiệu bắt đầu trên Stack • F ⊆ Q : tập các trạng thái kết thúc (nếu PDA chấp nhận chuỗi bằng Stack rỗng thì F = Ø)

Hoạt động của PDA

Chuyển đến trạng thái p.

07/11/2011

Thay Z trên đỉnh stack bằng α.

(cid:1) Hoạt động của PDA phụ thuộc vào hàm chuyển δ (cid:1) Nếu δ(q, a, Z) có (p, α) là một trong các kết quả thì một trong các hành động mà PDA làm tại trạng thái q, với a ở đầu chuỗi nhập, và Z ở trên đỉnh stack là: 1. 2. Xóa a khỏi đầu chuỗi nhập ( a có thể là ε). 3.

PDAPDA

Hàm chuyển δ:

• Hàm chuyển phụ thuộc ký hiệu nhập

δ(q, a, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) }

• Hàm chuyển không phụ thuộc ký hiệu nhập

δ(q, ε, Z) = { (p1, γ1), (p2, γ2), ..., (pm, γm) }

Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng 1) δ(q1, 0, R) = {(q1, BR)} 2)δ(q1, 1, R) = {(q1, YR)} 3)δ(q1, 0, B) = {(q1, BB)} 4)δ(q1, 1, B) = {(q1, YB)} 5)δ(q1, 0, Y) = {(q1, BY)} 6)δ(q1, 1, Y) = {(q1, YY)}

7) δ(q1, c, R) = {(q2, R)} 8) δ(q1, c, B) = {(q2, B)} 9) δ(q1, c, Y) = {(q2, Y)} 10) δ(q2, 0, B) = {(q2, ε)} 11) δ(q2, 1, Y) = {(q2, ε)} 12) δ(q2, ε, R) = {(q2, ε)}

PDAPDA

Hình thái (ID - instantaneous description): dùng để ghi nhớ

trạng thái và nội dung của Stack

(q, aw, Zα) ⊢⊢⊢⊢

M (p, w, βα) nếu δ(q, a, Z) chứa (p, β)

Ngôn ngữ chấp nhận bởi PDA:

• Ngôn ngữ được chấp nhận bằng trạng thái kết thúc

L (M) = {w | (q0, w, Z0) ⊢* (p, ε, γ) với p ∈∈∈∈ F và γ ∈∈∈∈ Γ*}

• Ngôn ngữ được chấp nhận bởi Stack rỗng

N (M) = {w | (q0, w, Z0) ⊢* (p, ε, ε) với p ∈∈∈∈ Q}

Ví dụ: PDA chấp nhận wcwR bằng Stack rỗng với chuỗi nhập 001c100

(q1, 001c100, R) ⊢ (q1, 01c100, BR) ⊢ (q1, 1c100, BBR) ⊢ (q1, c100, YBBR) ⊢ (q2, 100, YBBR) ⊢ (q2, 00, BBR) ⊢ (q2, 0, BR) ⊢ (q2, ε, R) ⊢ (q2, ε, ε) : Chấp nhận

07/11/2011

(DPDA) PDA đơnđơn địnhđịnh (DPDA) PDA

Ví dụ: thiết kế PDA chấp nhận {wwR | w ∈∈∈∈ (0 + 1)*} bằng Stack rỗng • Không có ký hiệu c để biết thời điểm chuyển từ trạng thái q1 sang q2 • Bắt buộc phải đoán thử (khi thấy 2 ký hiệu liên tiếp giống nhau)

絃 Nếu ký hiệu thuộc chuỗi xuôi : giữ nguyên trạng thái q1 và push vào Stack 絃 Nếu ký hiệu thuộc chuỗi ngược : chuyển sang trạng thái q2 và pop khỏi Stack

• M({q1, q2}, {0, 1}, {R, B, Y}, δ, q1, R, Ø):

1) 2) 3) 4) 5)

6) δ(q1, 1, Y) = {(q1, YY),(q2, ε)} δ(q1, 0, R) = {(q1, BR)} δ(q1, 1, R) = {(q1,YR)} 7) δ(q2, 0, B) = {(q2, ε)} δ(q1, 0, B) = {(q1, BB), (q2, ε)} 8) δ(q2, 1, Y) = {(q2, ε)} 9) δ(q1, ε, R) = {(q2, ε)} δ(q1, 0, Y) = {(q1, BY)} 10) δ(q2, ε, R) = {(q2, ε)} δ(q1, 1, B) = {(q1, YB)}

(DPDA) PDA đơnđơn địnhđịnh (DPDA) PDA

Ví dụ: các phép chuyển hình thái của PDA chấp nhận chuỗi 001100

thuộc ngôn ngữ {wwR | w ∈∈∈∈ (0 + 1)*} bằng Stack rỗng

Khởi đầu

↓

↓ (q1, 001100, R) ↓ (q1, 01100, BR) → (q2, 1100, R) → (q2, 1100, ε) : Không chấp nhận ↓ (q1, 1100, BBR) ↓ (q1, 100, YBBR) → (q2, 00, BBR) ↓ (q1, 00, YYBBR) (q2, 0, BR) → (q2, ε, R) → (q2, ε, ε) : Chấp nhận ↓ (q1, 0, BYYBBR) → (q2, ε, YYBBR) : Không chấp nhận ↓ (q1, ε, BBYYBBR) : Không chấp nhận

07/11/2011

(DPDA) PDA đơnđơn địnhđịnh (DPDA) PDA

Định nghĩa: một PDA M(Q, Σ, Γ, δ, q0, Z0, F) được gọi là đơn định

nếu:

• ∀q ∈∈∈∈ Q và Z ∈∈∈∈ Γ: nếu δ(q, ε, Z) ≠ Ø thì δ(q, a, Z) = Ø với ∀a ∈∈∈∈ Σ • Không có q ∈∈∈∈ Q, Z ∈∈∈∈ Γ và a ∈∈∈∈ (Σ ∪ {ε}) mà δ(q, a, Z) chứa nhiều hơn một phần tử

Chú ý: đối với PDA thì dạng đơn định và không đơn định là không

tương đương nhau.

Ví dụ: wwR được chấp nhận bởi PDA không đơn định, nhưng không

được chấp nhận bởi bất kỳ một PDA đơn định nào.

07/11/2011

Định lý 6.1: Nếu một ngôn ngữ phi ngữ cảnh L được chấp nhận bởi một PDA chấp nhận chuỗi bởi trạng thái kết thúc M2 thì L cũng được chấp nhận bởi một PDA chấp nhận chuỗi bởi Stack rỗng M1

Cách xây dựng:

Đặt M2(Q, Σ, Γ, δ, q0, Z0, F) và M1(Q ∪ {qe, q0'}, Σ, Γ, δ', q0', X0, Ø) • δ'(q0', ε, X0) = {(q0, Z0X0)} • δ'(q, a, Z) chứa mọi phần tử của δ(q, a, Z) với a ∈∈∈∈ (Σ ∪ {ε}) • δ'(q, ε, Z) chứa (qe, ε) với ∀q ∈∈∈∈ F và Z ∈∈∈∈ (Γ ∪ {X0}) • δ'(qe, ε, Z) chứa (qe, ε) với ∀Z ∈∈∈∈ (Γ ∪ {X0})

Tương đương Tương đương giữagiữa PDA Stack rỗngrỗng vàvà PDA PDA vớivới PDA vớivới Stack thúc thái kếtkết thúc trạng thái trạng

07/11/2011

Định lý 6.2: Nếu một ngôn ngữ phi ngữ cảnh L được chấp nhận bởi

một PDA chấp nhận chuỗi bởi Stack rỗng M1 thì L cũng được chấp nhận bởi một PDA chấp nhận chuỗi bởi trạng thái kết thúc

M2Cách xây dựng:

Đặt M1(Q, Σ, Γ, δ, q0, Z0, F) và M2(Q ∪ {q0', qf}, Σ, Γ ∪ {X0}, δ', q0', X0, {qf})

• δ'(q0', ε, X0) = {(q0, Z0X0)} • δ'(q, a, Z) = δ(q, a, Z) với a ∈∈∈∈ (Σ ∪ {ε}) • δ'(q, ε, X0) chứa (qf, ε) với ∀q ∈∈∈∈ Q

Tương đương Tương

đương giữagiữa PDA

PDA vàvà CFLCFL

Định lý 6.4: Nếu L được chấp nhận bởi một PDA chấp nhận chuỗi

bởi Stack rỗng thì L là ngôn ngữ phi ngữ cảnh

Cách xây dựng:

Đặt PDA M(Q, Σ, Γ, δ, q0, Z0, Ø) chấp nhận L với Stack rỗng Đặt G(V, T, P, S) là CFG, trong đó:

• V là tập các đối tượng dạng [q, A, p] • S là ký hiệu bắt đầu mới được thêm vào • P là tập các luật sinh dạng

1. S → [q0, Z0, q] với ∀q ∈∈∈∈ Q 2. [q, A, qm+1] → a [q1, B1, q2][q2, B2, q3]...[qm, Bm, qm+1]

sao cho δ(q, a, A) có chứa (q1, B1B2...Bm) Nếu m = 0 thì luật sinh có dạng [q, A, q1] → a

Tương đương Tương đương giữagiữa PDA Stack rỗngrỗng vàvà PDA PDA vớivới PDA vớivới Stack thúc thái kếtkết thúc trạng thái trạng

Tương đương Tương

đương giữagiữa PDA

PDA vàvà CFLCFL

Ví dụ: xây dựng CFG tương đương sinh ra ngôn ngữ được chấp nhận bởi PDA M({q0, q1}, {0, 1}, {Z0, X}, δ, q0, Z0, Ø) với δ như sau:1. δ(q0, 0, Z0) = {(q0, XZ0)} 2. δ(q0, 0, X) = {(q0, XX)} 3. δ(q0, 1, X) = {(q1, ε)}

4. δ(q1, 1, X) = {(q1, ε)} 5. δ(q1, ε, X) = {(q1, ε)} 6. δ(q1, ε, Z0) = {(q1, ε)}

Xây dựng: CFG G(V, {0, 1}, P, S) 1. Tập các biến V = [q, A, p] ∪ S

= { S, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1],

[q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1]

}

2. Tập các luật sinh P

S → [q0, Z0, q0] | [q0, Z0, q1]

δ1) [q0, Z0, q0] → 0 [q0, X, q0] [q0, Z0, q0] | 0 [q0, X, q1] [q1, Z0, q0] [q0, Z0, q1] → 0 [q0, X, q0] [q0, Z0, q1] | 0 [q0, X, q1] [q1, Z0, q1]

Tương đương Tương

đương giữagiữa PDA

PDA vàvà CFLCFL

δ3) [q0, X, q1] → 1 δ4) [q1, X, q1] → 1

δ2) [q0, X, q0] → 0 [q0, X, q0] [q0, X, q0] | 0 [q0, X, q1] [q1, X, q0] [q0, X, q1] → 0 [q0, X, q0] [q0, X, q1] | 0 [q0, X, q1] [q1, X, q1] δ5) [q1, X, q1] → ε δ6) [q1, Z0, q1] → ε

Đặt: [q0, X, q0] = A, [q0, X, q1] = B, ..., [q0, Z0, q0] = E, ..., [q1, Z0, q1] =

S → 0B B → 0B | 0B1 | 1

Giản lược văn phạm: S → F F → 0BH B → 0BD | 1 D → ε | 1 H → ε

07/11/2011

CÂU HỎI VÀ BÀI TẬP CHƯƠNG 05 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 05

Chương 6:

Turing MáyMáy Turing achine) uring MMachine)

((TTuring

Nội dung:

• Mô hình TM

• TM nhận dạng ngôn ngữ

• TM tính toán hàm số nguyên

• Các kỹ thuật xây dựng TM

MôMô hìnhhình TMTM

Định nghĩa: TM là một hệ thống gồm 7 thành phần

M (Q, Σ, Γ, δ, q0, B, F)

● Q : tập hữu hạn các trạng thái ● Σ : bộ ký hiệu nhập ● Γ : tập hữu hạn các ký hiệu được viết trên băng ● δ : hàm chuyển Q x Γ → Q x Γ x {L, R, Ø} ● q0 : trạng thái khởi đầu ● B : ký hiệu dùng để chỉ khoảng trống trên băng ● F ⊆ Q : tập các trạng thái kết thúc

Hình thái: α1qα2 với q là trạng thái hiện hành của TM, α1α2 là nội

dung của băng tính từ đầu băng cho đến ký hiệu khác Blank bên phải nhất

07/11/2011

chuyển PhépPhép chuyển

Định nghĩa: Đặt X1X2...Xi-1qXi...Xn là một hình thái (ID)

Giả sử : δ(q, Xi) = (p, Y, L) • Nếu i - 1 = n thì Xi là B • Nếu i = 1 thì không có ID kế tiếp (đầu đọc không được phép vượt qua cận trái của băng. • Nếu i > 1 ta viết:

⊢ X1X2...Xi-2pXi-1YXi+1...Xn

X1X2...Xi-1qXi...Xn Tương tự : δ(q, Xi) = (p, Y, R) X1X2...Xi-1qXi...Xn

⊢ X1X2...Xi-2Xi-1YpXi+1...Xn

Và với : δ(q, Xi) = (p, Y, Ø)

X1X2...Xi-1qXi...Xn

⊢ X1X2...Xi-2Xi-1pYXi+1...Xn

TM TM nhậnnhận dạngdạng ngônngôn ngữngữ

Định nghĩa: ngôn ngữ được chấp nhận bởi TM M là

L(M) = {w | w∈∈∈∈ Γ* và q0w ⊢ α1pα2 với p∈∈∈∈ F}

Ví dụ: thiết kế TM chấp nhận L = {0n1n | n > 0}

Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với Q = {q0, q1, q2, q3, q4}, Γ = {0, 1, X, Y, B}, F = {q4}

⊢⊢⊢⊢ XXYYq4

Xét chuỗi 0011 ta có: q00011 ⊢⊢⊢⊢ Xq1011 ⊢⊢⊢⊢ X0q111 ⊢⊢⊢⊢ X q20Y1 ⊢⊢⊢⊢ q2X0Y1 ⊢⊢⊢⊢ X q00Y1 ⊢⊢⊢⊢ XXq1Y1 ⊢⊢⊢⊢ XXY q11 ⊢⊢⊢⊢ XX q2YY ⊢⊢⊢⊢ X q2XYY ⊢⊢⊢⊢ XX q0YY ⊢⊢⊢⊢ XXYq3Y ⊢⊢⊢⊢ XXYYq3

07/11/2011

nguyên TM TM nhưnhư làlà máymáy tínhtính hàmhàm sốsố nguyên

Quy ước: một số nguyên trong TM được viết dưới dạng nhất phân

là một chuỗi số 0, cách nhau bởi 1 số 1.

000001001000B = 5, 2, 3

Ví dụ: thiết kế TM tính toán phép trừ riêng

• Nếu m < n thì m \ n = 0 • Ngược lại thì m \ n = m – n • Input: 0m10nB

Output: 0m\nB

Đặt TM M(Q, Σ, Γ, δ, q0, B, F) với • Q = {q0, q1, q2, q3, q4, q5, q6}, Γ = {0, 1, B}, F = {q6}

KỹKỹ thuật

thuật lưulưu trữtrữ trong

khiển trong bộbộ điềuđiều khiển

Ví dụ: thiết kế TM kiểm tra ký tự đầu tiên của một chuỗi không xuất

hiện ở bất kỳ vị trí nào khác trong chuỗi.

Xây dựng: TM M(Q, {0, 1}, {0, 1, B}, δ, [q0, B], B, F)

trong đó các trạng thái thuộc Q là một cặp {q0, q1} x {0, 1, B} F = {[q1, B]}

Phép chuyển:

δ([q0, B], 0) = ([q1, 0], 0, R) δ([q1, 0], 0) = ([q1, 0], 0, R) δ([q1, 0], B) = ([q1, B], B, Ø) δ([q0, B], 1) = ([q1, 1], 1, R) δ([q1, 1], 1) = ([q1, 1], 1, R) δ([q1, 1], B) = ([q1, B], B, Ø)

07/11/2011

KỹKỹ thuật

qua (Shifting over) thuật dịchdịch qua (Shifting over)

Ví dụ: thiết kế máy Turing để dịch một chuỗi các ký hiệu khác B sang

phải 2 ô

Xây dựng: TM M(Q, Σ, Γ, δ, q0, B, F)

trong đó Q chứa các phần tử dạng [q, A1, A2] với q = q1 hoặc q2; A1 và A2 thuộc Γ. Trạng thái bắt đầu là [q1, B, B]

Phép chuyển:

δ([q1, B, B], A1) = ([q1, B, A1], X, R) (X là ký hiệu đặc biệt nào đó) δ([q1, B, A1], A2) = ([q1, A1, A2], X, R) δ([q1, A1, A2], A3) = ([q1, A2, A3], A1, R) ... δ([q1, Ai-2, Ai-1], Ai) = ([q1, Ai-1, Ai], Ai-2, R) ... δ([q1, An-1, An], B) = ([q2, An, B], An-1, R) δ([q2, An, B], B) = ([q2, B, B], An, L)

KỹKỹ thuật

thuật chương

chương trình

trình concon

Ví dụ: thiết kế TM thực hiện phép nhân 2 số nguyên dương m và n

• Input: 0m10nB • Output: 0m*nB • Ý tưởng: đặt số 1 sau 0m10n (0m10n1), sau đó chép n số 0 sang phải m lần, mỗi lần xóa đi 1 số 0 bên trái của m • Sau khi m đã được xóa, phép nhân đã được thực hiện xong, xóa tiếp 10n1. Kếu quả còn lại sẽ là B0m*nB

Phân tích:

• Xóa 1 số 0 bên trái của m, dịch đầu đọc sang số n để chuẩn bị cho việc copy n số 0: q00m10n1 ⊢⊢⊢⊢ B0m-11q10n1 • Copy n số 0 sang phải: B0m-11q10n1 ⊢⊢⊢⊢ B0m-11q50n10n • Quay lại trạng thái bắt đầu: B0m-11q50n10n ⊢⊢⊢⊢ Bq00m-110n10n • Chuẩn bị cho việc copy kế tiếp:

B0m-11q50n10n ⊢⊢⊢⊢ B20m-21q10n10n

• Copy n số 0 sang phải ...

07/11/2011

KỹKỹ thuật

thuật chương

chương trình

trình concon

Thủ tục copy n số 0:

δδδδ(q6, 1) = (q1, 1, R)

Biến đổi hình thái q00m10n1 ⊢⊢⊢⊢ B0m-11q10n1: δδδδ(q6, 0) = (q6, 0, R) δδδδ(q0, 0) = (q6, B, R) Biến đổi hình thái Bi0m-i1q50n10n*i ⊢⊢⊢⊢ Bi+10m-i-11q10n10n*i:

07/11/2011

CÂU HỎI VÀ BÀI TẬP CHƯƠNG 06 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 06

Chương 7:

Ứng dụng automat trong Ứng dụng automat trong ngôn ngữ và thiết kế số ngôn ngữ và thiết kế số

Nội dung:

• Ứng dụng trong trình biên dịch

• Ứng dụng trong thiết kế số

Ứng dụng automat trong trong Ứng dụng automat trong trong biên dịch thiết kế trình biên dịch thiết kế trình

Khoa KTMT

Vũ Đức Lung

07/11/2011

Xây dựng văn phạm cho ngôn ngữ lập trình

(cid:1)(cid:1) Văn Văn phạphạm đệ qui m đệ qui (cid:2) Cho văn phạm PNC G, với A là ký hiệu không kết thúc và

(cid:3) Nếu α = ∈, đệ qui trái (cid:3) Nếu β = ∈, đệ qui phải

nếu tồn tại A → αAβ thì A là ký hiệu đệ qui và G là văn phạm đệ qui

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:1)(cid:1) Loại bỏ đệ quy trái: Loại bỏ đệ quy trái: (cid:2) Các phương pháp phân tích từ trên xuống không thể nào xử lý văn phạm đệ qui trái, do đó cần phải dùng một cơ chế biến đổi tương đương để loại bỏ các đệ qui trái.

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng văn phạm cho ngôn ngữ lập trình

07/11/2011

Xây dựng văn phạm cho ngôn ngữ lập trình

(cid:1) Ví dụ 2: Loại bỏ đệ quy trái cho văn phạm:

E → TE’ E’ → +TE’ | ∈ T → FT’ T’ → *FT’ | ∈

Khoa KTMT - UIT

TS. Vũ Đức Lung

E -> E + T | T T -> T * F | F F -> (E) | id

Xây dựng văn phạm cho ngôn ngữ lập trình

(cid:1) Giải thuật 4.1: Loại bỏ đệ quy trái

Khoa KTMT - UIT

TS. Vũ Đức Lung

Nhập: Văn phạm G không có vòng lặp hoặc luật sinh rỗng. Xuất: Văn phạm tương đương G’ không có đệ quy trái. Phương pháp: G’ không còn đệ quy trái nhưng có thể có luật sinh rỗng.

07/11/2011

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng văn phạm cho ngôn ngữ lập trình

(cid:1) Ví dụ 3: Áp dụng giải thuật 4.1 vào văn phạm sau để loại bỏ

đệ quy trái. S ->Aa | b A -> Ac | Sd | ∈ Các bước thực hiện: - - - Sắp xếp: S, A Thay S vào A: A -> Ac | Aad | bd | ∈ Loại bỏ đệ qui trái:

Khoa KTMT - UIT

TS. Vũ Đức Lung

S (cid:4) Aa | b A (cid:4) bdA’ | ∈A’ A’ (cid:4) cA’ | adA’ | ∈

Thừa số trái

07/11/2011

(cid:1) Ví dụ 4: Có hai luật sinh:

stmt -> if exp then stmt else stmt | if exp then stmt

Khoa KTMT - UIT

TS. Vũ Đức Lung

Tạo văn phạm có thừa số trái

(cid:1) Cả hai luật sinh đều có if dẫn đầu nên ta sẽ không biết chọn luật sinh nào để triển khai. Vì thế để làm chậm lại quyết định lựa chọn ta sẽ tạo ra thừa số trái.

Nhập: Cho văn phạm G. Xuất: Văn phạm G’ có thừa số trái tương đương. Phương pháp: Tìm chuỗi dẫn đầu chung của các vế phải luật sinh, ví dụ:

Khoa KTMT - UIT

TS. Vũ Đức Lung

γ là chuỗi không bắt đầu bởi α. Ta thay các luật trên bằng các luật A -> αA’ | γ A’-> β1 | β2 | β3 … | βn

Thừa số trái

07/11/2011

(cid:1) Ví dụ 5 : Cho văn phạm như sau

S -> iEtS | iEtSeS | a E -> b

(cid:1) Áp dụng giải thuật trên cho văn phạm phát biểu if, ta có văn

Khoa KTMT - UIT

TS. Vũ Đức Lung

Phân tích cú pháp từ trên xuống

phạm yếu tố trái như sau. S -> iEtSS’ | a S’-> eS | ∈ E -> b

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:1) Phân tích cú pháp đệ quy. (cid:1) Phân tích cú pháp không đệ quy.

Phân tích cú pháp đệ quy đi xuống

07/11/2011

(cid:1) Ví dụ 6 : Cho văn phạm G:

S -> cAd A -> ab | a

Khoa KTMT - UIT

TS. Vũ Đức Lung

Phân tích cú pháp đoán ỨỨng ng dụdụng ng 11: : Phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy

(cid:1) Các bước phân tích cú pháp từ trên xuống:

(cid:1) Loại bỏ đệ quy trái cho văn phạm mà ta thiết kế. (cid:1) Tạo văn phạm có thừa số trái nếu cần thiết. (cid:1) Sơ đồ dịch cho bộ phân tích đoán nhận trước.

token đó.

(cid:2) Nếu có sự truyền trên ký hiệu không kết thúcA thì ta thực hiện một

lệnh gọi thủ tục A.

Khoa KTMT - UIT

TS. Vũ Đức Lung

Sơ đồ này có đặc điểm như sau: (cid:2) Mỗi ký hiệu không kết thúc có một sơ đồ. (cid:2) Tên các cạnh là token và các ký hiệu không kết thúc. (cid:2) Sự truyền trên token sẽ được thực hiện nếu ký hiệu nhập trùng với

Phân tích cú pháp đoán Phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy

07/11/2011

(cid:1) Để xây dựng sơ đồ ta sẽ tiến hành các bước sau đây:

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:2) Tạo trạng thái bắt đầu và kết thúc. (cid:2) Với mỗi luật sinh có dạng: A -> X1X2…Xn ta xây dựng đường đi từ trạng thái bắt đầu đến trạng thái kết thúc sao cho các cạnh có tên X1, X2, X3…Xn.

Ví dụ 7: Tạo sơ đồ dịch cho văn phạm G

(cid:1)

Cơ chế hoạt động của bộ phân tích cú pháp đoán nhận trước đệ quy

Khoa KTMT - UIT

TS. Vũ Đức Lung

E → E + T | T T → T * F | F F → (E) | id Loại bỏ đệ quy trái trong văn phạm, ta được văn phạm tương đương sau : E -> TE’ E’-> + TE’| ∈ T -> FT’ T’-> *FT’| ∈ F -> (E) | id Sơ đồ dịch của các ký hiệu không kết thúc của G

Bộ phân tích cú pháp đoán Bộ phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy

07/11/2011

Sơ đồ dịch của các ký hiệu không kết thúc của G

Khoa KTMT - UIT

TS. Vũ Đức Lung

Bộ phân tích cú pháp đoán Bộ phân tích cú pháp đoán nhận trước đệ quy nhận trước đệ quy

Ví dụ: phân tích câu id*(id + id)

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:5) Sơ đồ dịch của các ký hiệu không kết thúc của G đã được thu giảm

Giải thuật

Khoa KTMT - UIT

TS. Vũ Đức Lung

Bộ phân tích cú pháp LR ỨỨng ng dụdụng ng 22: : Bộ phân tích cú pháp LR

(cid:1)

07/11/2011

Khoa KTMT - UIT

TS. Vũ Đức Lung

Các tính chất của phương pháp phân tích LR: Bộ phân tích LR có thể nhận dạng được cấu trúc cú pháp của các ngôn ngữ lập trình do văn phạm phi ngữ cảnh tạo ra. Phương pháp LR là phương pháp tổng quát nhất của phương pháp phân tích đẩy và thu giảm, không bị quay lui từ trước đến giờ. Lớp văn phạm được phân tích bằng phương pháp LR là lớp văn phạm cha, bao trùm lớp văn phạm được phân tích bởi phương pháp đoán nhận trước. Bộ phân tích có khả năng phát hiện lỗi sớm nhất khi nó rà đến ký hiệu nhập từ trái sang phải.

Cấu tạo bộ phân tích cú pháp LR

Khoa KTMT - UIT

TS. Vũ Đức Lung

Hoạt động

07/11/2011

(cid:1) Stack được dùng để chứa chuỗi ký hiệu có dạng

s0X1s1X2…Xmsm, với sm nằm trên đỉnh stack, Xi được gọi là ký hiệu văn phạm, si là trạng thái. Cặp(si, Xi) sẽ xác định một trị được lưu chứa trong bảng phân tích. Bảng phân tích gồm hai phần biểu thị bởi hàm action và goto. (cid:1) Cấu hình (configuration) của bộ phân tích LR là một cặp (nội dung stack nội dung còn lại của chuỗi nhập)

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:1) Ví dụ: (s0X1s1…Xisi…Xmsm, aiai+1…an$).

Phân tích cú pháp LR

07/11/2011

(cid:1) Nhập: chuỗi nhập w, bảng phân tích action goto của văn phạm G.

(cid:1) Xuất: nếu w thuộc L (G), nó tạo ra sự phân tích từ dưới lên. Ngược lại, bộ phân tích sẽ báo lỗi.

(cid:1) Phương pháp:

Khoa KTMT - UIT

TS. Vũ Đức Lung

Phân tích cú pháp LR

Khoa KTMT - UIT

TS. Vũ Đức Lung

Thời điểm ban đầu stack có trạng thái s0. Chuỗi w$ nằm trên bộ đệm nhập. Bộ phân tích đặt đầu đọc (con trỏ ip) vào ký hiệu nhập đầu tiên của w.

Ví dụ

07/11/2011

Khoa KTMT - UIT

TS. Vũ Đức Lung

Bảng phân tích cho văn phạm G

Khoa KTMT - UIT

TS. Vũ Đức Lung

Cho văn phạmG (1) E -> E + T (2) E -> T (3) T -> T * F (4) T -> F (5) F -> (E) (6) F -> id Phân tích câu w = id *id + id

Ví dụ

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng bảng phân tích SLR

07/11/2011

Định nghĩa: thực thể LR (0) gọi tắt là thực thể của văn phạm G là luật sinh của G với các điểm chấm ở các vị trí nào đó của vế phải. Thí dụ: G có luật sinh A -> XYZ, sẽ cho bốn thực thể: A->•XYZ A->X•YZ A->XY•Z A->XYZ• Nếu A -> ∈ sẽ cho ta thực thể A ->•

Định nghĩa văn phạm gia tố: nếu G là văn phạm có S là ký hiệu

Khoa KTMT - UIT

TS. Vũ Đức Lung

mục tiêu, thì G’ là văn phạm gia tố có S’ là ký hiệu mục tiêu và có thêm luật sinh S’->S ngoài các luật sinh trong G

Giải thuật tính bao đóng–Closure.

Function closure (I : item) : item; begin J := I; repeat

sinh

for với mỗi thực thể A -> a.Bß trong J và với mỗi luật B -> γ trong G sao cho thực thể B -> •γ chưa có trong J do thêm B -> •γ vào J; until không thể thêm thực thể mới vào J;

closure := J;

end;

Khoa KTMT - UIT

TS. Vũ Đức Lung

Ví dụ

07/11/2011

(cid:1) Xét văn phạm gia tố của biểu thức:

Khoa KTMT - UIT

TS. Vũ Đức Lung

E' → E E → E + T | T T → T * F | F F → (E) | id

Ví dụ

07/11/2011

Khoa KTMT - UIT

TS. Vũ Đức Lung

Giải thuật tính goto

Nếu I là tập hợp chỉ gồm văn phạm { E'→ • E } thì closure(I), gọi là I0 bao gồm: E' → • E E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id

(cid:1) Goto(I, X), trong đó I là một tập các mục và X là một ký

hiệu văn phạm là bao đóng của tập hợp các mục A → αX•β sao cho A → α•Xβ € I.

(cid:1) Cách tính goto(I, X): 1. Tạo một tập I' = ∅. 2. Nếu A → α•Xβ € I thì đưa A→ αX•β vào I', tiếp tục quá trình này cho đến khi xét hết tập I.

Khoa KTMT - UIT

TS. Vũ Đức Lung

3. Goto(I, X) = closure(I')

Ví dụ

07/11/2011

(cid:1) Giả sử I = { E' → E•, E → E • + T }.

Tính goto (I, +) ?

(cid:1) Ta có I' = { E→ E + • T } (theo luật 2)

goto (I, +) = closure(I') bao gồm các mục :

Khoa KTMT - UIT

TS. Vũ Đức Lung

E → E + • T (Luật 1) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2)

Giải thuật tính tập tuyển các tập thực thể

Procedure items (G’); begin

C := {closure ({S’->•S}}} repeat for với mỗi tập thực thể I trong C và với mỗi ký hiệu văn phạm X sao cho phép goto(I, X) không rỗng và không có trong C do thêm goto(I, X) vào C; until không thể thêm tập thực thể mới vào C;

Khoa KTMT - UIT

TS. Vũ Đức Lung

end;

Xây dựng bảng phân tích

(cid:1) (cid:1) (cid:1)

Nhập: văn phạm gia tố G’ Xuất: bảng phân tích SLR với hàm action và goto cho văn phạm G’ Phương pháp:

1. Xây dựng C = {Io, I1, …In}. 2. i là trạng thái đại diện cho tập thực thể Ii.

a. Nếu A -> α•aß là thực thể ở trong Ii và goto(Ii, a) = Ij thì phần tử action[i, a] = shift(j), với a phải là ký hiệu kết thúc. b. Nếu A -> α• ở trong Ii thì action[i, a] = reduce(A -> α) với a là tất cả các ký hiệu nằm trong follow(A). A không phải là S’(ký hiệu mục tiêu mới).

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng bảng phân tích

07/11/2011

c. Nếu S’->S• ở trong Ii thì action [i, $] = accept. 3. Cho tất cả các ký hiệu không kết thúc A. Nếu goto[Ii, A] = Ij thì hàm goto[i, A] = j.

4. Tất cả các phần tử của bảng phân tích không được xác định bằng quy tắc 2 và 3, chúng ta coi là lỗi.

Khoa KTMT - UIT

TS. Vũ Đức Lung

5 Trạng thái bắt đầu của bộ phân tích là tập thực thể có chứa thực thể S’-> •S.

Ví dụ

Cho văn phạm gia tố G’

E’-> E E -> E + T E -> T T -> T* F T -> F F -> (E) F -> id

Hãy tìm tập C và sơ đồ DFA. Xây dựng bảng phân tích SLR

Khoa KTMT - UIT

TS. Vũ Đức Lung

Ví dụ

07/11/2011

(cid:1) Văn phạm gia tố G’:

Khoa KTMT - UIT

TS. Vũ Đức Lung

(0) E'→ E (1) E → E + T (2) E → T (3) T → T * F (4) T → F (5) F → (E) (6) F → id

Xây dựng tập C

I0 : E'→ • E

E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng tập C

(cid:5) Ban đầu sẽ xét trạng thái I0 cho tập C vừa tạo Tập ký hiệu văn phạm cho I0: “E,T,F,(,id “ (các ký hiệu theo sau dấu • là goto

được=>chọn)

Goto(I0,E) I1= E’->E•

(tìm những luật sinh có •E và đổi thành E•)

E->E•+T

Tính closure(E’->E•) không có kết quả do sau • không có ký hiệu Tính closure(E->E•+T) không có kết quả do sau • là +: ký hiệu kết

thúc, không có luật sinh

=>closure(I1) = Rỗng

Goto(I0,T) I2= E->T•

T->T•*F closure(I2) = rỗng

Goto(I0,F) I3= T->F•

Khoa KTMT - UIT

TS. Vũ Đức Lung

07/11/2011

Xây dựng tập C

07/11/2011

Goto(I0,() I4= F->(•E)

closure(I4) = closure(F->(•E)) E->•E+T

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng tập C

E->•T T->•T*F T->•F F->•(E) F->•id Goto(I0,id) I5= F->id•

E->E+•T closure(I6) = closure(E+•T)

T->•T*F T->•F F->•(E) F->•id

(cid:5) Xét trên tập I1: Goto(I1,+) I6=

Goto(I2,*) I7=

E->T*•F closure(I6) = closure(T*•F)

F->•(E) F->•id

Khoa KTMT - UIT

TS. Vũ Đức Lung

(cid:5) Xét tiếp I2: tập ký tự văn phạm: *

Xây dựng bảng phân tích

Tính action của các trạng thái

(cid:1) (cid:5) Tính shift (cid:5) Xét I0: E’->•E E->•E+T E->•T T->•T*F T->•F F->•(E) F->•id Tìm các luật sinh có dạng: A -> α•aß (a là ký tự kết thúc) để tính action. Ở I0 có luật:

F->•(E) có ( là ký tự kết thúc. Ta có goto(I0,() = I4 nên action[0,(] = s4 (shifft(4)) F->•id mà goto(I0,id) = I5 =>action[0,id]=s5

(cid:5) Xét I1: E’->E• E->E•+T

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng bảng phân tích

Xét I2:

E->T• E->T•*F Ta có goto(I2,*)=I7 => action[2,*]=s7

Xét I3: không có dạng A -> α•aß Xét I4:

F->(•E) E->•E+T E->•T T->•T*F T->•F F->•(E) F->•id goto(I4,()=I4 =>action[4,(]=s4 goto(I4,id)=I5 =>action[4,id]=s5

Khoa KTMT - UIT

TS. Vũ Đức Lung

07/11/2011

Xây dựng bảng phân tích

(cid:5) Xét I5: không có dạng: A -> α•aß (cid:5) Xét I6:

E->E+•T T->•T*F T->•F F->•(E) F->•id goto(I6,()=I4=> action[6,(]=s4 goto(I6,id)=I5=> action[6,id]=s5

(cid:5) Xét I7: E->T*•F F->•(E) F->•id goto(I7,() = I4 =>action[7,(]=s4 goto(I7,id) = I5 =>action[7,id]=s5

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng bảng phân tích

07/11/2011

(cid:5) Xét I8: F->(E•) E->E•+T goto(I8,)) = I10=>action[8,)]=s10 goto(I8,+)=I6=>action[8,+]=s6

E->E+T• T->T•*F goto(I9,*) =I7=>action[9,*]=s7 Xét I10: không có dạng A -> α•aß Xét I11: không có dạng A -> α•aß

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xét I9:

Tính Follow

(cid:1) FOLLOW(E) = {+, ), $} (cid:1) FOLLOW(T) = {*, +, ), $} (cid:1) FOLLOW(F) = {*, +, ), $}

Khoa KTMT - UIT

TS. Vũ Đức Lung

Xây dựng bảng phân tích

(cid:5) Tính Reduce:

Xét các trạng thái mà có luật sinh dạng: A -> α• I0: không có luật sinh dạng A -> α• I1: Có E’->E• thuộc dạng A -> α• mà cũng thuộc dạng: S’->S• vì E là ký hiệu mục

tiêu nên ta có: action[1,$]=accept I2: có E->T• là luật sinh thứ 2 trong G Tính follow(E)={+,),$} =>action[2,+] = action[2,)]= action[2,$] = r2 I3: có T->F• là luật sinh thứ 4 trong G follow(T) = {*,$} U folow(E) = {+,),*,$} Nên action[3,+] = action[3,)] = action[3,*] = action[3,$] = r4 I4: không có luật sinh dạng A -> α• I5: có F->id• là luật sinh thứ 6 trong G follow(F) = follow(T) = {+,),*,$} action[5,+] action[5,)] = action[5,*] = action[5,$] = r6

Khoa KTMT - UIT

TS. Vũ Đức Lung

07/11/2011

Xây dựng bảng phân tích

07/11/2011

I6,I7,I8 không có luật sinh dạng A -> α• I9: E->E+T• là luật sinh thứ 1 trong G Tính follow(E)={+,),$} action[9,+] = action[9,)] = action[9,$] = r1 I10: E->T*F• là luật sinh 4 Tính follow(E)={+,),$} action[9,+] = action[9,)] = action[9,$] = r4 I11: F-> (E)• là luật sinh 5 follow(F) = {+,),*,$}Các ký hiệu kết thúcCác ký hiệu không kết thúcDò action[0,id] = s5goto(I0,E) =>I1

Khoa KTMT - UIT

TS. Vũ Đức Lung

trong thiết Ứng dụng automat trong thiết Ứng dụng automat kế số kế số

Khoa KTMT

Vũ Đức Lung

action[11,+] = action[11,)] = action[11,*] = action[11,$] = r5

Giới thiệu

07/11/2011

Electronics Systems

Analog Systems Digital Systems

Sequential Combinational

Khoa KTMT

Vũ Đức Lung

Giới thiệu (tt)

Synchronuos Asynchronuos

Ngõ vào

Ngõ ra

MẠCH TỔ HỢP

PHẦN TỬ NHỚ

Khoa KTMT

Vũ Đức Lung

(cid:5) Mạch logic tuần tự là mạch có các ngõ ra tùy thuộc không chỉ vào trạng thái hiện tại của các ngõ vào mà còn tùy thuộc vào một chuỗi các ngõ vào trước đó.

Các mạch chốt

07/11/2011

(cid:5) Flip_Flop: là mạch tuần tự mà nó thường lấy mẫu các ngõ vào và làm thay đổi các ngõ ra tại những thời điểm xác định bởi xung clock.

(cid:5) Latch (chốt): là mạch tuần tự mà nó liên tục xem xét các ngõ

LATCH

Ungated latch

Gated latch

Khoa KTMT

Vũ Đức Lung

Ungated SR Latch

vào và làm thay đổi các ngõ ra bất cứ thời điểm nào không phụ thuộc vào xung clock.

Q(t+1)

0 Q(t) No change

R (Reset)

0 Clear to 0

1 Set to 1

1 X Indeterminate

S (Set)

Khoa KTMT

Vũ Đức Lung

(cid:5) Dùng cổng NOR:

Ungated SR-Latch (tt)

07/11/2011

S R

Qt+1Qt+1

(cid:5) Dùng cổng NAND:

.

S (Set)

Cấm

0 0 0 1 1 0 1 1

1 1 1 0 0 1 Qt Qt

.

R (Reset)

Khoa KTMT

Vũ Đức Lung

Gated SR-latch

Ngõ vào cho phép C còn được gọi là ngõ vào xung clock (CK).

Khoa KTMT

Vũ Đức Lung

Chốt SR này còn được gọi là chốt SR có ngõ vào xung clock tích cực cao.

D latch

D D

Q(t+1) Q(t+1)

0 0

0 Clear to 0 0 Clear to 0

1 1

1 Set to 1 1 Set to 1

_ Q

AND2

NOR2

AND2

NOT

Khoa KTMT

Vũ Đức Lung

JK latch

07/11/2011

KJ KJ

Q(t+1) Q(t+1)

0 0

Q(t) No change Q(t) No change

0 0

1 1

0 Clear to 0 0 Clear to 0

1 1

0 0

1 Set to 1 1 Set to 1

)(tQ

1 1

Complement Complement

Khoa KTMT

Vũ Đức Lung

(cid:5) Từ mạch lật SR (cid:5) Khắc phục nhược điểm của SR

T latch

07/11/2011

T T 0 0

Q(t+1) Q(t+1) Q(t) No change Q(t) No change

)(tQ

1 1

Complement Complement

Khoa KTMT

Vũ Đức Lung

Flip-flop Chủ tớ

(cid:5) Từ JK latch (cid:5) Nối J với K

(cid:5) Gated latch có nhược điểm: xung clock phải đủ ngắn để đảm bảo nội dung của linh kiện nhớ chỉ cập nhật một lần cho mỗi xung

Master Latch

Slave Latch

S Q C

Khoa KTMT

Vũ Đức Lung

(cid:5) Giải pháp: điều khiển theo cấu hình chủ tớ

Flip-flop kích cạnh

07/11/2011

D D

Q Q

C C

Q+ Q+ 1 0 0 1

Khoâng ñoåi Khoâng ñoåi

CK D 0 1 x 0 x 1

Clock

Output cannot change

Chuyển tiếp lề dương

Khoa KTMT

Vũ Đức Lung

D-FF kích cạnh lên

Biểu đồ trạng thái

Time

Khoa KTMT

(cid:5) Flip-flop D với chuyển tiếp dương:

Đồ thị dạng tín hiệu Vũ Đức Lung

D-FF kích cạnh xuống

07/11/2011

Khoa KTMT

Vũ Đức Lung

T-FF kích cạnh

Khoa KTMT

Vũ Đức Lung

(cid:5) Flip-flop D với chuyển tiếp âm

T-FF kích cạnh xuống

Khoa KTMT

Vũ Đức Lung

Bảng kích thích của bốn mạch Flip-flop

Q(t)

Q(t+1)

S R

Q(t)

Q(t+1)

07/11/2011

0 X

X 0

Q(t)

Q(t+1)

J K

Q(t)

Q(t+1)

0 X

D SR

X 0

Khoa KTMT

Vũ Đức Lung

JK T

Các ngõ vào bất đồng bộ

07/11/2011

(cid:5) Preset (Pr) và Clear (Cl): Các ngõ vào này sẽ làm thay đổi giá

trị ngõ ra tức thời, bất chấp xung clock – Khi ngõ vào Preset tích cực thì ngõ ra Q được set lên 1. – Khi ngõ vào Clear tích cực thì ngõ ra Q được xóa về 0.

Khoa KTMT

Vũ Đức Lung

Chuyển đổi giữa các loại Flip-flops

(cid:5) Vd: IC 74LS47 gồm 2 D-FF

Q(t) là các biến của hàm

– Rút gọn hàm – Vẽ Mạch

(cid:5) Đa số trên thực tế các loại flip-flop được sản xuất: D và JK (cid:5) Quá trình chuyển đổi gồm các bườc sau: – Lập bảng kích thích của cả 2 loại flip-flop – Coi các ngõ vào của FF nguồn là hàm, còn các ngõ vào của FF đích +

– Chuyển đổi Flip-flop JK thành T – JK thành D – RS thành JK

Khoa KTMT

Vũ Đức Lung

(cid:5) Ví dụ:

Ứng dụng của các Flip-flop

07/11/2011

Khoa KTMT

Vũ Đức Lung

Bộ Đếm (COUNTER)

(cid:5) Công tắc triệt tiêu bounce (cid:5) Các bộ ghi (cid:5) Các bộ đếm (cid:5) Bộ nhớ truy cập ngẫu nhiên

(cid:5) Bộ đếm là hệ tuần tự có 1 ngõ vào xung clock và nhiều ngõ ra. Bộ đếm bao gồm nhiều Flip-Flop ghép lại với nhau, và các ngõ ra của FF chính là các ngõ ra của bộ đếm

Q2Q1Q0

000

(cid:5) Khái niệm: Trạng thái của bộ đếm, modulo của bộ đếm. (cid:5) Nếu m = 2n thì ta có bộ đếm đầy đủ, ngược lại nếu m < 2n thì ta có bộ đếm không đầy đủ

100

001

m = 5

011

101

Khoa KTMT

Vũ Đức Lung

(cid:5) Vd: Bộ đếm nhị phân 3 bit có giản đồ trạng thái sau:

Bộ đếm nối tiếp (Asynchronous Counter)

07/11/2011

Q0 (LSB)

Q2 (MSB)

(cid:5) Bộ đếm lên (Count Up):

.

(LSB) Q0

(MSB) Q2

Vũ Đức Lung

Khoa KTMT

Bộ đếm nối tiếp (tt)

Q0 (LSB)

Q2 (MSB)

(LSB) Q0

(MSB) Q2

Khoa KTMT

Vũ Đức Lung

(cid:5) Bộ đếm xuống (Count Down):

Bộ đếm nối tiếp (tt)

07/11/2011

Q0 (LSB)

Q2 (MSB)

Khoa KTMT

Vũ Đức Lung

Bộ đếm song song (Synchronous Counter)

(cid:5) Bộ đếm không đầy đủ (m < 2n): Dùng trạng thái cuối để tạo ra tín hiệu tác động tích cực vào các ngõ vào bất đồng bộ Preset hoặc Clear để đưa bộ đếm trở về trạng thái ban đầu (cid:5) Vd: Sử dụng T-FF có ngõ vào Preset và Clear tích cực mực thấp, thiết kế bộ đếm từ giá trị 0 đến 4 (m=5).

- Từ phát biểu bài toán xác định số FF cần dùng và dãy đếm. - Lập bảng chuyển trạng thái chỉ rõ mối quan hệ giữa trạng thái hiện tại và

trạng thái kế tiếp (dựa vào dãy đếm).

- Tìm các giá trị ngõ vào FF cần phải có từ giá trị hiện tại Q(t) và kế tiếp

Q(t+1) của từng FF (dựa vào bảng kích thích của mỗi loại FF).

- Tìm biểu thức rút gọn của mỗi ngõ vào FF phụ thuộc vào các biến trạng

thái hiện tại.

- Thực hiện sơ đồ logic.

(cid:5) Các bước thiết kế:

Khoa KTMT

Vũ Đức Lung

(cid:5) Vd: Sử dụng T-FF kích theo cạnh lên, thiết kế bộ đếm có dãy đếm sau: Q2Q1Q0 = 010, 101, 110, 001, 000, 111, 100, 011, 010, …

Bộ đếm song song (tt)

07/11/2011

(cid:5) Bộ đếm không đầy đủ (m < 2n): (cid:5) Khi thiết kế bộ đếm không đầy đủ, thì các trạng thái có trong

Q2Q1Q0

000

100

001

m = 5

vòng đếm sẽ thiết kế như bộ đếm đầy đủ; còn các trạng thái dư không có trong vòng đếm sẽ giải quyết theo 2 cách sau: * Cách 1: Các trạng thái dư không có vòng đếm có trạng thái kế tiếp là tùy định.

011

101

Khoa KTMT

Vũ Đức Lung

Bộ đếm song song (tt)

(cid:5) Vd: Thiết kế bộ đếm dùng D-FF cạnh lên, có ngõ vào Pr và CL tích cực cao, có giản đồ trạng thái sau:

Q2Q1Q0

000

010

111

100

001

m = 5

110

011

101

Khoa KTMT

Vũ Đức Lung

(cid:5) * Cách 2: Cho các trạng thái dư không có vòng đếm có trạng thái kế tiếp là 1 trong những trạng thái có trong vòng đếm. (cid:5) Vd: Cho 3 trạng thái dư không có trong vòng đếm có trạng thái kế tiếp như hình vẽ

Phân tích bộ đếm song song

07/11/2011

(cid:5) Từ sơ đồ logic của bộ đếm xác định hàm kích thích (biểu thức của các ngõ vào) của từng FF phụ thuộc vào các ngõ ra Qi. (cid:5) Lập bảng trạng thái: từ trạng thái hiện tại Qi và giá trị ngõ vào ta xác định được trạng thái kế tiếp của FF Q+i.

Khoa KTMT

Vũ Đức Lung

Phân tích bộ đếm song song (tt)

(cid:5) Từ bảng chuyển trạng thái xác định được giản đồ trạng thái hoặc khảo sát giản đồ xung của bộ đếm.

Q0 (LSB)

Q2 (MSB)

. . .

CK2

CK1

CK2

Khoa KTMT

Vũ Đức Lung

(cid:5) Vd: Hãy xác định giản đồ trạng thái của bộ đếm sau:

Bộ Đếm Thanh Ghi Dịch (Shift Register Counter)

07/11/2011

(cid:5) Bộ đếm vòng (Ring Counter): ngõ ra của thanh ghi dịch hồi

CK2

CK1

CK0

Khoa KTMT

Vũ Đức Lung

Bộ Đếm Thanh Ghi Dịch (tt)

tiếp về ngõ vào FF. Q2

(cid:5) Bộ đếm vòng xoắn (Twisted-ring Counter): còn gọi bộ đếm

Johnson Giống như bộ đếm vòng nhưng lấy ngõ ra đảo hồi tiếp về ngõ vào FF.

.

CK2

CK1

CK0

Khoa KTMT

Vũ Đức Lung

Máy trạng thái Máy trạng thái

07/11/2011

Khoa KTMT

Vũ Đức Lung

Khái niệm máy trạng thái

(cid:5) Máy trạng thái kiểu Moore (cid:5) Máy trạng thái kiểu Mealy

(cid:5) Hệ tuần tự ~ Máy trạng thái thuật toán (algorithmic state

machine) ~ Máy trạng thái (State Machine - SM) – Giản đồ trạng thái – Lưu đồ SM

State Machine

MOORE Q+ = f(Q,X) Z = g(Q)

MEALY Q+ = f(Q,X) Z = g(Q, X)

Khoa KTMT

Vũ Đức Lung

(cid:5) Dùng điều khiển một HTS thực hiện từng bước một

Máy MOORE

07/11/2011

Mạch Logic Mạch Logic tổ hợp tổ hợp

Mạch Logic tổ hợp

Clock

Khoa KTMT

Vũ Đức Lung

Máy MEALY

XX ZZ

Mạch Logic tổ hợp

Clock

Khoa KTMT

Vũ Đức Lung

ZZ XX

Lưu đồ máy trạng thái

07/11/2011

010

Output list

Output List

Hộp xuất theo điều kiện

Hộp trạng thái

Điều kiện X

Hộp điều kiện

Khoa KTMT

Vũ Đức Lung

Lưu đồ máy trạng thái (tt)

(cid:5) Các thành phần chính của lưu đồ SM

Khoa KTMT

Vũ Đức Lung

(cid:5) Gồm các khối SM (cid:5) VD:

Lưu đồ máy trạng thái (tt)

07/11/2011

???

Khoa KTMT

Vũ Đức Lung

Lưu đồ máy trạng thái (tt)

(cid:5) Một khối SM có thể có nhiều cách tương đương

Khoa KTMT

Vũ Đức Lung

(cid:5) Khối song song khối nối tiếp

Chuyển giản đồ trạng thái sang lưu đồ SM

07/11/2011

(cid:5) Ví dụ cho giản đồ sau:

Khoa KTMT

Vũ Đức Lung

Thành lập lưu đồ SM

(cid:5) Hãy chuyển giản đồ sang lưu đồ SM

(cid:5) Các bước thành lập: – Xác định bài toán – Xác định tín hiệu vào và ra – Xây dựng lưu đồ SM

Khoa KTMT

Vũ Đức Lung

(cid:5) Ví dụ: Vẽ lưu đồ SM của hệ kiểm tra chẵn lẻ số bit nhận được ở ngõ vào x, nếu số bit 1 nhận được từ ngõ vào x là số lẻ thì Z=1, là số chẵn thì Z=0.

Thiết kế SM bằng lưu đồ SM

07/11/2011

Thiết kế một mạch dãy đồng bộ thực hiện nhiệm vụ kiểm tra dãy tín hiệu vào ở dạng nhị phân có độ dài bằng 3 được đưa vào liên tiếp vào x. Nếu dãy tín hiệu vào có dạng 010 hoặc 011 hoặc 110 hoặc 111 thì tín hiệu ra Z=1 để báo hiệu là mạch đã nhận được một trong các dãy tín hiệu vào đó

Khoa KTMT

Vũ Đức Lung

Thiết kế SM bằng lưu đồ SM

(cid:5) Các bước thiết kế: – Xác định bài toán – Xác định tín hiệu vào và ra – Xây dựng lưu đồ SM, bảng trạng thái và tín hiệu ra – Tối thiểu các trạng thái dùng phương pháp Caldwell – Mã hóa trạng thái – Tìm hệ phương trình của mạch dựa vào bảng trạng thái rút gọn – Vẽ sơ đồ (cid:5) Ví dụ thiết kế:

Thiết kế một mạch dãy đồng bộ nhận biết dãy tín hiệu vào, tín hiệu vào được đưa liên tiếp ở đầu vào X của mạch theo dạng nhị phân, mỗi lần dãy tín hiệu vào là 101, mạch sẽ cho ra tín hiệu Z=1, các bít dữ liệu vào được đồng bộ với xung nhịp Clock.

Khoa KTMT

Vũ Đức Lung

(cid:5) Ví dụ 2: Thiết kế bằng hai loại Moore và Mealy

Các ví dụ thiết kế

07/11/2011

Lối đi vào

Lối đi ra

X1 X2

Khoa KTMT

Vũ Đức Lung

Các ví dụ thiết kế (tt)

(cid:5) VD1: Thiết kế mạch đếm để đếm số người vào thăm một viện bảo tàng và hiển thị số người hiện đang bên trong bảo tàng , mạch gồm 2 LED sáng X1 và X2 được bố trí như hình vẽ. Mạch thiết kế sao cho mỗi lần đếm được một người

bơm nước vào một ống nước nhờ 2 bơm p1 và P2, cả 2 bơm được mở để bơm nước khi mực nước ở dưới mức 1 và vẫn mở cho đến khi chưa đạt mức 2. Khi vừa đạt mức 2 thì bơm P1 ngắt, còn P2 vẫn bơm. Và P1 vẫn ngắt cho đến khi nước lại ở dưới mức 1, P2 vẫn mở, chỉ khi nước đạt mức3 thì P2 mới ngắt. Và P2 vẫn ngắt, chỉ mở khi nuớc lại xuống dưới mức 1

Khoa KTMT

Vũ Đức Lung

(cid:5) VD2: Thiết kế mạch điều khiển

Điều khiển bơm nước

07/11/2011

Khoa KTMT

Vũ Đức Lung

(cid:5) Mã hoá trạng thái: + a=1 khi mức nước lớn hơn huặc bằng mức 1, trường hợp khác a=0 + b=1 khi mức nước lớn hơn huặc bằng mức 2, trường hợp khác b=0 + c=1 khi mức nước lớn hơn huặc bằng mức 3, trường hợp khác c=0 + P=1 : Bơm mở; P=0 : bơm đóng

CHƯƠNG 07 CÂU HỎI VÀ BÀI TẬP CHƯƠNG 07 CÂU HỎI VÀ BÀI TẬP