2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩42頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、Yinliang ZhaoXi’an Jiaotong University2013,Pushdown Automata,2024/3/21,2,Pushdown Automata,A PDA is an automaton equivalent to the CFG in language-defining power.Only the nondeterministic PDA defines all possible CFL’

2、s.But the deterministic version models parsers.Most programming languages have deterministic PDA’s.,2024/3/21,3,Intuition: PDA,Think of an ?-NFA with the additional power that it can manipulate a stack.Its moves are d

3、etermined by:The current state (of its “NFA”),The current input symbol (or ?), and The current symbol on top of its stack.,2024/3/21,4,Intuition: PDA – (2),Being nondeterministic, the PDA can have a choice of next mov

4、es.In each choice, the PDA can:Change state, and alsoReplace the top symbol on the stack by a sequence of zero or more symbols.Zero symbols = “ pop.”Many symbols = one “ pop” and then sequence of “pushes.”,2024/3/21

5、,5,PDA Formalism,A PDA is described by:A finite set of states (Q, typically).An input alphabet (?, typically).A stack alphabet (?, typically).A transition function (?, typically).A start state (q0, in Q, typica

6、lly).A start symbol (Z0, in ?, typically).A set of final states (F ? Q, typically).,2024/3/21,6,Conventions,a, b, … are input symbols.But sometimes we allow ? as a possible value.…, X, Y, Z are stack symbols.…, w,

7、 x, y, z are strings of input symbols.?, ?,… are strings of stack symbols.,2024/3/21,7,The Transition Function,Takes three arguments:A state, in Q.An input, which is either a symbol in ? or ?.A stack symbol in ?.?(q

8、, a, Z) is a set of zero or more actions of the form (p, ?).p is a state; ? is a string of stack symbols.,2024/3/21,8,Actions of the PDA,If ?(q, a, Z) contains (p, ?) among its actions, then one thing the PDA can do in

9、state q, with a at the front of the input, and Z on top of the stack is:Change the state to p.Remove a from the front of the input (but a may be ?).Replace Z on the top of the stack by ?.,2024/3/21,9,Example: PDA,De

10、sign a PDA to accept {0n1n | n > 1}.The states:q = start state. We are in state q if we have seen only 0’s so far.p = we’ve seen at least one 1 and may now proceed only if the inputs are 1’s.f = final state; acce

11、pt.,2024/3/21,10,Example: PDA – (2),The stack symbols:Z0 = start symbol. Also marks the bottom of the stack, so we know when we have counted the same number of 1’s as 0’s.X = marker, used to count the number of 0’s se

12、en on the input.,2024/3/21,11,Example: PDA – (3),The transitions:?(q, 0, Z0) = {(q, XZ0)}.?(q, 0, X) = {(q, XX)}. These two rules cause one X to be pushed onto the stack for each 0 read from the input.?(q, 1, X) = {(

13、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.,Design a PDA to accept {0n1n | n > 1}.,2024/3/21,12,Actions of the Example PDA,

14、q,0 0 0 1 1 1,,Z0,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,13,Actions of the Example PDA,q,0 0 1 1 1,,XZ0,,?(q, 0, Z0) = {(q, XZ0)}?

15、(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,14,Actions of the Example PDA,q,0 1 1 1,,XXZ0,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?

16、(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,15,Actions of the Example PDA,q,1 1 1,,XXXZ0,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},

17、2024/3/21,16,Actions of the Example PDA,p,1 1,,XXZ0,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,17,Actions of the Example PDA,p,1,,XZ0

18、,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,18,Actions of the Example PDA,p,,Z0,,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1,

19、 X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,19,Actions of the Example PDA,f,,Z0,,2024/3/21,20,Instantaneous Descriptions,We can formalize the pictures just seen with an instantaneous descriptio

20、n (ID).A ID is a triple (q, w, ?), where:q is the current state.w is the remaining input.? is the stack contents, top at the left.,2024/3/21,21,The “Goes-To” Relation,To say that ID I can become ID J in one move of

21、the PDA, we write I ? J.Formally, (q, aw, X?) ? (p, w, ??) for any w and ?, if ?(q, a, X) contains (p, ?).Extend ? to ?*, meaning “zero or more moves,” by:Basis: I ?* I.Induction: If I ?* J and J ? K, then I ?* K.,20

22、24/3/21,22,Example: Goes-To,Using the previous example PDA, 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

23、),Thus, (q, 000111, Z0) ?*(f, ?, Z0).What would happen on input 0001111?,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,23,Answer,(q, 000111

24、1, 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.

25、What would happen on input 0000111?,Legal because a PDA can use ? input even if input remains.,?(q, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21

26、,24,Answer,(q, 0000111, Z0) ?(q, 000111, XZ0) ?(q, 00111, XXZ0) ?(q, 0111, XXXZ0) ? (q, 111, XXXXZ0) ?(p, 11, XXXZ0) ?(p, 1, XXZ0) ?(p, ?, XZ0) 0000111 is not accepted, because the final state f is not reached.,?(q

27、, 0, Z0) = {(q, XZ0)}?(q, 0, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,25,Principles about IDs,Theorem 6.5: If for a PDA, (q, x, A) ?* (p, y, B), then for any string

28、w?∑* and ???*, it is also true that:(q, xw, A?) ?* (p, yw, B?)Theorem 6.6: If for a PDA, (q, xw, A) ?* (p, yw, B), then it is also true that:(q, x, A) ?* (p, y, B),2024/3/21,26,Aside: FA and PDA Notations,We represe

29、nted moves of a FA by an extended ?, which did not mention the input yet to be read.We could have chosen a similar notation for PDA’s, where the FA state is replaced by a state-stack combination, like the pictures just

30、shown.,2024/3/21,27,FA and PDA Notations – (2),Similarly, we could have chosen a FA notation with ID’s.Just drop the stack component.Why the difference? FA tend to model things like protocols, with indefinitely long i

31、nputs.PDA model parsers, which are given a fixed program to process.,2024/3/21,28,PDA transition diagram,Formally, (q, aw, X?) ? (p, w, ??) for any w and ?, if ?(q, a, X) contains (p, ?).,?(q, 0, Z0) = {(q, XZ0)}?(q, 0

32、, X) = {(q, XX)}?(q, 1, X) = {(p, ?)}?(p, 1, X) = {(p, ?)}?(p, ?, Z0) = {(f, Z0)},2024/3/21,29,Ex.2: language of balanced parenthesis,q0,,(, Z0 / ( Z0,?, Z0 / Z0,?, Z0 / Z0,,,Grow stack,Switch topopping mode,Pop stac

33、k for matching symbols,Go to acceptance (by final state)when you see the stack bottom symbol,∑ = { (, ) }= {Z0, ( }Q = {q0,q1,q2},(, ( / ( (,), ( / ?,), ( / ?,,To allow adjacentblocks of nested paranthesis,(, ( /

34、 ( (,(, Z0 / ( Z0,?, Z0 / Z0,2024/3/21,30,Ex.2: language of balanced parentheses (another design),∑ = { (, ) }= {Z0, ( }Q = {q0,q1},q0,,,(,Z0 / ( Z0(,( / ( (), ( / ?,start,,,q1,?,Z0/ Z0,?,Z0/ Z0,2024/3/21,31,Language

35、 of a PDA,The common way to define the language of a PDA is by final state.If P is a PDA, then L(P) is the set of strings w such that (q0, w, Z0) ?* (f, ?, ?) for final state f and any ?.,2024/3/21,32,Language of a PDA

36、– (2),Another language defined by the same PDA is by empty stack.If P is a PDA, then N(P) is the set of strings w such that (q0, w, Z0) ?* (q, ?, ?) for any state q.,2024/3/21,33,Equivalence of Language Definitions,If L

37、 = L(P), then there is another PDA P’ such that L = N(P’). Theorem6.11 L(P)= N(P’) If L = N(P), then there is another PDA P’’ such that L = L(P’’). Theorem6.9 N(P)= L(P’’),2024/3/21,34,Proof: L

38、(P) ? N(P’) Intuition,P’ will simulate P.If P accepts, P’ will empty its stack.P’ has to avoid accidentally emptying its stack, so it uses a special bottom-marker to catch the case where P empties its stack without acc

39、epting.,2024/3/21,35,Proof: L(P) ? N(P’),P’ has all the states, symbols, and moves of P, plus:Stack symbol X0, used to guard the stack bottom against accidental emptying.New start state s and “erase” state e.?(s, ?, X

40、0) = {(q0, Z0X0)}. Get P started.?(f, ?, X) = ?(e, ?, X) = {(e, ?)} for any final state f of P and any stack symbol X.,2024/3/21,36,Example: L of balanced parenthesis,q0,,,(,Z0 / ( Z0(,( / ( (), ( / ?,start,,,q1,?,Z0

41、/ Z0,?,Z0/ Z0,PDA that accepts by final state,PF:,PN:,How will these two PDAs work on the input: ( ( ( ) ) ( ) ) ( ),2024/3/21,37,Proof: N(P) ? L(P’’) Intuition,P” simulates P.P” has a special bottom-marker to catch th

42、e situation where P empties its stack.If so, P” accepts.,2024/3/21,38,Proof: N(P) ? L(P’’),P’’ has all the states, symbols, and moves of P, plus:Stack symbol X0, used to guard the stack bottom.New start state s and fi

43、nal state f.?(s, ?, X0) = {(q0, Z0X0)}. Get P started.?(q, ?, X0) = {(f, ?)} for any state q of P.,2024/3/21,39,Example: Matching parenthesis “(” “)”,,PN:( {q0}, {(,)}, {Z0,Z1}, δN, q0, Z0 )δN:δN(q0,(,Z0) = { (q0,

44、Z1Z0) }δN(q0,(,Z1) = { (q0, Z1Z1) }δN(q0,),Z1) = { (q0, ?) }δN(q0, ?,Z0) = { (q0, ?) },Pf:( {p0,q0 ,pf}, {(,)}, {X0,Z0,Z1}, δf, p0, X0 , pf)δf:δf(p0, ?, X0) = { (q0, Z0X0) }δf(q0, (, Z0) = { (q0, Z1Z0) }δf(

45、q0, (, Z1) = { (q0, Z1Z1) }δf(q0, ), Z1) = { (q0, ?) }δf(q0, ?, Z0) = { (q0, ?) }δf(q0, ?, X0) = { (pf, ? ) },,Accept by empty stack,Accept by final state,2024/3/21,40,Deterministic PDA’s,To be deterministic, there

46、 must be at most one choice of move for any state q, input symbol a, and stack symbol X.In addition, there must not be a choice between using input ? or real input.Formally, ?(q, a, X) and ?(q, ?, X) cannot both be non

47、empty.?(q, a, X) has at most one member for any a???{?}If ?(q, a, X) is non-empty for some a??, then ?(q, ?, X) must be empty.,2024/3/21,41,This PDA for Lwwr is non-deterministic,q0,,q1,,q2,,,0, Z0/0Z01, Z0/1Z00, 0

48、/000, 1/011, 0/101, 1/11,0, 0/ ?1, 1/ ?,?, Z0/Z0 ?, 0/0 ?, 1/1,?, Z0/Z0,,,Grow stack,Switch topopping mode,Pop stack for matching symbols,Accepts by final state,Why does it have to be non-deterministic?,To remo

49、ve guessing, impose the user to insert c in the middle,2024/3/21,42,D-PDA for Lwcwr,q0,,q1,,q2,,,0, Z0/0Z01, Z0/1Z00, 0/000, 1/011, 0/101, 1/11,0, 0/ ?1, 1/ ?,c, Z0/Z0 c, 0/0 c, 1/1,?, Z0/Z0,,,Grow stack,Switch t

50、opopping mode,Pop stack for matching symbols,Accepts byfinal state,Note: all transitions have become deterministic,Example shows that: Nondeterministic PDAs ≠ D-PDAs,Lwcwr = {wcwR | c is some special symbol not in w}

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論