24
Example: Goes-To
The previous PA of {0n1n | n > 1} We can describe the sequence of moves by:
(q, 000111, Z0)⊦ (q, 00111, XZ0)⊦ (q, 0111, XXZ0)⊦ (q, 111, XXXZ0)⊦ (p, 11, XXZ0)⊦ (p, 1, XZ0)⊦ (p, ε, Z0)⊦ (f, ε, Z0) (q, 000111, Z0)
29
Proof: L(P) -> N(P’) 直观思考
用P’模拟 P. Idea:
当P接收时，将P'的栈置空. 特殊情况：栈空且没有接收的情况 用一个特殊的栈底标记来表示栈空且没有接
收的情况
30
Proof: L(P) -> N(P’)
P’ 包含P的所有状态、符号、以及迁移， 另外:
1. 栈符号X0 (used to identify the stack bottom against accidental emptying) 2. New start state s and “erase” state e. 3. δ(s, ε, X0) = {(q0, Z0X0)}. Get P started. 4. δ(f, ε, X) = δ(e, ε, X) = {(e, ε)} for any final state f of P and any stack symbol X.
28
Equivalence of Language Definitions
1. For any L(P), there exists a PA P' such that N(P')=L(P). 2. For any N(P'), there exists a PA P'' such that L(P'')=N(P').
1. 2. 3. 4. 5. 6. 7. Q, a finite set of states 与有限状态自动机 Σ, an input alphabet 的区别是什么？ 的区别是什么？ Γ, a stack alphabet δ, a transition function 栈！ q0 in Q, a start state Z0 in Γ, a start stack symbol F ⊆ Q, a set of final states
31
Proof: L(P) -> N(P’)
start
ε, X/ε s q0 ε, X0/Z0X0 P e ε, X/ε ε, X/ε
32
Proof: N(P) -> L(P’’) 直观思考
P” simulates P. P” 通过一个特殊的栈底标志来表示P的 栈为空的情况 If so, P” accepts.
13
Example
迁移：
δ(q, 0, Z0) = {(q, XZ0)}. δ(q, 0, X) = {(q, XX)}. These two rules cause one X to be pushed into the stack for each 0 read from the input. δ(q, 1, X) = {(p, ε)}. When we see a 1, go to state p and pop one X. δ(p, 1, X) = {(p, ε)}. Pop one X per 1. δ(p, ε, Z0) = {(f, Z0)}. Accept at bottom.
1. q, a state in Q 2. a, an input, which is either a symbol in Σ or ε 3. Z, A stack symbol in Γ
函数δ(q, a, Z) 的结果为 a set of actions of the form (p, α)
p is a state; α is a string of stack symbols. 为什么是a set of actions?
*
(f, ε, Z0)
25
What would happen on input 0001111?
Answer
Legal because a PA can use ε input even if input remains. δ(p, ε, Z0) = {(f, Z0)}
(q, 0001111, Z0)⊦(q, 001111, XZ0)⊦ (q, 01111, XXZ0)⊦(q, 1111, XXXZ0)⊦ (p, 111, XXZ0)⊦(p, 11, XZ0)⊦ (p, 1, Z0)⊦(f, 1, Z0) Note the last ID has no move. 0001111 is not accepted, because the input is not completely consumed.
Pushdown Automata 下推自动机
Pushdown Automata
正则语言
正则文法 有限状态自动机
上下文无关语言
上下文无关文法 下推自动机(PA)
2
Pushdown Automata
正则语言
正则文法 NFA = DFA
上下文无关语言
上下文无关文法 NPA (NPA ⊃ DPA)
DPA 仅定义了上下文无关语言一个真子集
6
常用符号
a, b, … 输入符号.
But sometimes we allow ε as a possible value.
…, X, Y, Z 栈符号 …, w, x, y, z 输入符号串 α, β,… 栈符号串
7
迁移函数
表达为： δ(q, a, Z)={(p1, α1), (p2, α2), ...} 函数δ有3个参数:
18
Actions of the Example PA
11
p
X X Z0
19
Actions of the Example PA
1
p
X Z0
20
Actions of the Example PA
p
Z0
21
Actions of the Example PA
f
Z0
22
PA的瞬时描述
瞬时描述(instantaneous description, ID) is a 3-triple (q, w, α) 表达了PA当前的情况:
4
PA的直观思考
在每次迁移中，PA做以下动作：
1. 改变状态 2. 将栈顶符号替换为一个长度可以为0符号序 列
长度为零时 = “pop” 出栈 长度大于0时 = sequence of “pushes”
5
PA 的形式化定义
A PA is defined by a seven tuple (Q, Σ, Γa PA
The common way to define the language of a PA is by final state. If P is a PA, then L(P) is the set of strings w such that (q0, w, Z0) ⊦* (f, ε, α) for final state f and any α.
大部分程序设计语言可以用DPA描述 DPA can model parsers
如果没有特殊说明，本节课中提及的PA一般都是 3 非确定PA
PA的直观思考
下推自动机可以看作是一个具有栈操作 能力的ε-NFA
PA = ε-NFA + 栈(及其操作)
PA迁移取决于:
1. 当前状态 2. 当前输入符号 (可以为 ε) 3. 当前栈顶符号
1. the current state, q. 2. the remaining input, w. 3. stack contents, α (top at the left)
23
The “Goes-To” Relation
Let I and J be two different IDs I⊦J: ID I can become ID J in one move of the PA Formally： (q, aw, Xα)⊦(p, w, βα) for any w and α, if δ(q, a, X) contains (p, β). Extend ⊦ to ⊦*, meaning “zero or more moves” .
0,0/ε 1,1/ε
11
Example
设计一个下推自动机接收语言 {0n1n | n > 1}. 状态: :
q = 初始状态.
• 到目前为止，只看到了0
p = we’ve seen at least one 1 and may now proceed only if the inputs are 1’s. f = final state
9
迁移函数
δ(q, a, Z)={(p1, α1), (p2, α2), ...} a, a1,a2,... a1,a2,...
q
pi
Z,Z1,..
αi, Z1, ...
10
PA的图形表示
是否可以像FSA那样，可以有一个PA的 图形表示？
1,Z0/1 ε,Z0/ε
q3
q1
q2
0,Ζ0/0 1,Ζ0/1
34
Proof: N(P) -> L(P’’)
ε, X0/ε ε, X0/ε s q0 ε, X0/Z0X0 P f ε, X0/ε ε, X/ε
start
35
Aside: FA and PDA Notations