tailieunhanh - Automata and Formal Language (chapter 7)

Chương 7 của bộ Slide tiếng Anh môn học lý thuyết automata và ngôn ngữ hình thức đầy đủ của trường ĐHBK . Bộ Slide này có tổng cộng 7 chương. | Chapter 7: Pushdown Automata Quan Thanh Tho qttho@ Pushdown Automata There are context-free languages that are not regular. Finite automata cannot recognize all context-free languages. Example {a, b}* is regular. {akbk | k is a constant} is regular. {anbn | n 0} is not regular. Pushdown Automata Control unit q0 Input file yes/no Stack Non-deterministic Pushdown Automata (NPDA) M = (Q, , , , q0, z, F) Q: finite set of internal states : finite set of symbols - input alphabet : finite set of symbols - stack alphabet : Q ( { }) finite subsets of Q * transition function q0 Q: initial state z : stack start symbol F Q: set of final states Transition Function : Q ( { }) finite subsets of Q * stack top stack top replacement Example (q1, a, b) = {(q2, cd), (q3, )} b d c q1 q2 q3 Example M = (Q, , , , q0, z, F) Q = {q0, q1, q2, q3} (q0, a, 0) = {(q1, 10), (q3, )} = {a, b} (q0, , 0) = {(q3, )} | Chapter 7: Pushdown Automata Quan Thanh Tho qttho@ Pushdown Automata There are context-free languages that are not regular. Finite automata cannot recognize all context-free languages. Example {a, b}* is regular. {akbk | k is a constant} is regular. {anbn | n 0} is not regular. Pushdown Automata Control unit q0 Input file yes/no Stack Non-deterministic Pushdown Automata (NPDA) M = (Q, , , , q0, z, F) Q: finite set of internal states : finite set of symbols - input alphabet : finite set of symbols - stack alphabet : Q ( { }) finite subsets of Q * transition function q0 Q: initial state z : stack start symbol F Q: set of final states Transition Function : Q ( { }) finite subsets of Q * stack top stack top replacement Example (q1, a, b) = {(q2, cd), (q3, )} b d c q1 q2 q3 Example M = (Q, , , , q0, z, F) Q = {q0, q1, q2, q3} (q0, a, 0) = {(q1, 10), (q3, )} = {a, b} (q0, , 0) = {(q3, )} = {0, 1} (q1, a, 1) = {(q1, 11)} z = 0 (q1, b, 1) = {(q2, )} F = {q3} (q2, b, 1) = {(q2, )} (q2, , 0) = {(q3, )} Instantaneous Description (q, w, u) current state unread part of stack contents input string Instantaneous Description Move move: (q1, aw, bx) | (q2, w, yx) iff (q2, y) (q1, a, b) Instantaneous Description Transition (q1, x, y) | *M (q2, u, v) (q1, x, y) | +M (q2, u, v) Language accepted by NPDA Let M = (Q, , , , q0, z, F) be an NPDA. L(M) = {w * | (q0, w, z) | *M (qf, , u), qf F, u *} Example L = {w {a, b}* | na(w) = nb(w)} M = (Q, , , , q0, z, F) Q = {q0, qf} (q0, , z) = {(qf, z)} = {a, b} (q0, a, z) = {(q0, 0z)} = {0, 1, z} (q0, b, z) = {(q0, 1z)} F = {qf} (q0, a, 0) = {(q0, 00)} (q0, b, 0) = {(q0, )} (q0, a, 1) = {(q0, )} (q0, b, 1) = {(q0, 11)} Example L = {wwR | w {a, b}+} M = (Q, , , , q0, z, F) Q = {q0, q1, q2} = {a, b} = {a, b, z} F = {q2} (q0, a, a) = {(q0, aa)} (q0, , a) = .