CS代写 COMP3630/6360: Theory of Computation Semester 1, 2022

COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University

This lecture covers Chapter 6 of HMU:
Language accepted by a PDA
Equivalence of CFGs and the languages accepted by PDAs Deterministic PDAs
Additional Reading: Chapter 6 of HMU.

Introduction to PDAs
ó PDA ‘=’ ε-NFA + Stack (LIFO)
ó At each instant, the PDA uses:
(a) the input symbol, if read; (b) present state; and (c) symbol atop the stack to transition to a new state and alter the top of the stack.
ó Once the string is read, the PDA decides to accept/reject the input string.
ó Note: The PDA can only read a symbol once (i.e., the reading head is unidirectional).
PDA ‘=’ Ý-NFA + Stack
Reading head
Internal Stack
Accept/Reject
Finite Control

PDA: Formal Definition
Definition
A PDA P = (Q,Σ,Γ,δ,q0,Z0,F) where
ó Just like in DFAs: Q is the (finite) set of internal states; Σ is the finite alphabet of input tape symbols; q0 ∈ Q is the (unique) start state; F is the set of final or accepting states of the PDA.
ó Γ is the finite alphabet of stack symbols;
ó δ : Q ×(Σ∪{ε})×Γ → 2Q×Γ∗ (power set of Q ×Γ∗) such that δ(q,a,γ) is always a
finite set of pairs (q′, γ′) ∈ Q × Γ∗.
ó Z0 ∈ Γ is the sole symbol atop the stack at the start; and
Input symbol (or Ý) Next state The number of possible transitions Present state Ü(qà aà A) = (qi0àâi) : i = 1à:::àÔ
Stack symbol on top The string replacing A on top of the stack
Convention: lower case symbols s, a, and b will denote input symbols; lower case symbols u, v, w will exclusively denote strings of input symbols; stack symbols are indicated by upper case letters (e.g., A, B, etc); strings of stack symbols are indicated by greek letters (e.g., α, β, etc);

A PDA Example
Transition Diagram Notation
Notation: The label a, A/γ on the edge from a state q to q′ indicates a possible transition from state q to state q′ by reading the symbol a when the top of the stack contains the symbol A. This stack symbol is then replaced by the string γ.
(q0àâ) 2 Ü(qàaàA) , q aàA=â q0 (Note: q0 can be q itself)
PDA that accepts L = {wwR : w ∈ {0.1}∗}
0à Z0=0Z0 1à Z0=1Z0 0à 0=00 1à 0=10 0à 1=01 1à 1=11
0à 0=Ý 1à 1=Ý
Ýà Z0=Z0
Ýà 0=0 Ýà 1=1
Ýà Z0=Z0

Language Accepted by a PDA
Language Accepted by a PDA
Definitions
ó The Configuration or Instantaneous Description (ID) of a PDA P is a triple (q,w,γ)∈Q×Σ∗×Γ∗ where:
(i) q is the state of the PDA;
(ii) w is the unread part of input string; and (iii) γ is the stack contents from top to bottom.
ó An ID tracks the trajectory/operation of the PDA as it reads the input string.
ó One-step computation of a PDA P, denoted by ⊢, indicates configuration change
due to one transition. Suppose (q′, γ) ∈ δ(q, a, A). For w ∈ Σ∗, α ∈ Γ∗, (q, aw, Aα) ⊢ (q′, w, γα), [one-step computation]
ó (multi-step) computation, denoted by ⊢, indicates configuration change due to zero P
or any finite number of consecutive PDA transitions.
ó ID ⊢ ID′ if there are k IDs ID1,…,IDk (for some k ≥ 1) such that:
(i) ID1 = ID and IDk = ID′, and
(ii) for each i = 1,…,k − 1, IDi ⊢ IDi+1. P

Language Accepted by a PDA
Beware of IDs!
Lemma 6.2.1
Let PDA P = (Q,Σ,Γ,δ,q0,Z0,F) be given. Let q,q′ ∈ Q, x,y,w ∈ Σ∗, and α, β, γ ∈ Σ∗. Then the following hold.
(q,x,α) ⊢ (q′,y,β) ⇔ (q,xw,α) ⊢ (q′,yw,β)
(q,x,α) ⊢ (q′,y,β) ⇒ (q,x,αγ) ⊢ (q′,y,βγ)
Proof Idea
ó (1) What hasn’t been read cannot affect configuration changes
ó (2) PDA transitions cannot occur on empty stack. So the (q, x, α) ⊢ (q′, y, β) must P
not access any location beneath the last symbol of x. Why is the reverse implication of (2) not true?

Language Accepted by a PDA
Language Accepted by PDAs
Definition
Given PDA P = (Q,Σ,Γ,δ,q0,Z0,F), the language accepted by P by final states is 􏰌∗􏰍
L(P)= w∈Σ∗ :(q0,w,Z0)⊢(q,ε,α)forsomeq∈F,α∈Γ∗ . P
The language accepted by P by empty(ing its) stack is
􏰌∗􏰍 N(P)= w∈Σ∗ :(q0,w,Z0)⊢(q,ε,ε)forsomeq∈Q .
Can L(P) and N(P) be different?
ó Pick a DFA A such that L(A) ̸= ∅. Convert it to a PDA P by pushing each symbol that is read onto the stack, increasing the stack size each time a symbol is read. For the derived PDA, L(P) = L(A). However, N(P) = ∅.
ó Which of the two definitions accepts ‘more’ languages?

Language Accepted by a PDA
Equivalence of the Two Notions of Language Acceptance
Theorem 6.2.2
Given PDA P, there exist PDAs P′ and P′′ such that L(P) = N(P′) and N(P) = L(P′′). Proof of Existence of P′′
PDA P PDA P00
Ýà Z0à Z0X0
ó Introduce a new start state and a new final state with the transitions as indicated.
ó The start state first replaces the stack symbol Z0 by Z0X0.
ó If and only if w ∈ N(P) will the computation by P end with the stack containing precisely X0.
ó The PDA P′′ then transitions to the final state popping X0. Hence, N(P) = L(P′′). 9/28

Language Accepted by a PDA
Equivalence of the two Notions of Language Acceptance
Proof of Existence of P′ such that L(P) = N(P′)
Ýà Z0à Z0X0
Ýà any=Ý
ó Introduce a new start state and a special state with the transitions as indicated.
ó The start state first replaces the stack symbol Z0 by Z0X0.
ó If and only if w ∈ L(P) will the computation by P end in a final state with the stack containing (at least) X0.
ó The PDA P′ then transitions to the special state and starts to pop stack symbols one at time until the stack is empty. Hence, L(P) = N(P′).
Ýà any=Ý
Ýà any=Ý
Ýà any=Ý

CFGs and PDAs
CFGs and PDAs
Is every CFL accepted by some PDA and vice versa?
Theorem 6.3.1
For every CFG G, there exists a PDA P such that N(P) = L(G).
ó Let G = (V,T,P,S) be given.
ó Construct PDA P = ({q0},T,V ∪ T,δ,S,{q0}) with δ defined by
[Type 1] δ(q0,a,a) = {(q0,ε)}, whenever a ∈ Σ,
[Type 2] δ(q0,ε,A) = {(q0,α) : A −→ α is a production rule in P}.
ó This PDA mimics all possible leftmost derivations. ó We use induction to show that L(G) = N(P)

CFGs and PDAs
CFGs and PDAs
Proof of 1-1 Correspondence between PDA Moves and Leftmost Derivations
Supposew∈T∗ andS⇒∗ w.
x\y:=suffixofyinx.
Vi 2V íi 2(V [T)⇤ S
UnreadPartof Input Tape
Stack StackSymbolsthat have been popped
[Type 2] [Type 1]
[Type 2] [Type 1]
[Type 2] [Type 1]
[Type 2] [Type 1]
A ¬ B := The suffix of B in A
Leftmost Derivation in Grammar G
Configurations in PDA P

CFGs and PDAs
CFGs and PDAs
Theorem 6.3.2
For every PDA P, there exists a CFG G such that L(G) = N(P).
ó Given P = (Q,Σ,Γ,δ,q0,Z0,F), we define G = (V,T,P,S) as follows. ó T = Σ;
ó V ={S}∪{[pXq]:p,q∈Q,X ∈Γ};
Interpretation: Each variable [pXq] will generate a terminal string w iff upon reading w (in finite steps) P moves from state p to q popping X from the stack.
ó P contains only the following rules:
ó S −→ [q0Z0p] for all p ∈ Q.
ó Suppose that (r,X1 ···Xl) ∈ δ(q,a,X). Then, for any states p1,…,pl ∈ Q,
[qXpl] −→ a[rX1p1][p2X2p2] · · · [pl−1Xlpl]. Note that if (r,ε) ∈ δ(q,a,X), then [qXr] −→ a.
ó We will show [qXp] ⇒ w ⇔ (q,w,X) ⊢ (p,ε,ε). The proof is complete by choosing GP
q = q0, X = Z0.

CFGs and PDAs
CFGs and PDAs
Proof of (q,w,X) ⊢ (p,ε,ε) ⇒ [qXp] ⇒ w. (Induction on # of steps of computation) PG
ó Basis: Let w ∈ N(P). Suppose there is a one-step computation (q,w,X) ⊢ (p,ε,ε). P
Then, w ∈ Σ ∪ {ε}. Since (p, ε) ∈ δ(q, w , X ), [qXp] −→ w is a production rule. ∗
ó Induction: Let (q, w , X ) ⊢ (p, ε, ε). Let a be read in the first step of the computation, P
and let w = ax. Then the following argument completes the proof.
1 (qàwàX) ` (r àxàY à:::àY )`⇤∗(pàÝàÝ) Defn. G [qXp] ! a [r1Y1r2][r2Y2r3]ààà[rkYkp]
P11kP)z z w=ax
2 A portion of x is read, and Y1 is popped; more is read, Y2 is popped,: : :
z=x ⇤ ⇤ ⇤⇤
(r1àw1w2 àààwÔàY1Y2 àààYk) `P (r2àw2 àààwkàY2 àààYk) `P (r3àw3 àààwkàY3 àààYk) ààà `P (rkàwkàYk) `P
(pàÝàÝ) + Induc.
(r1àw1àY1) [r1Y2r2] )⇤ w1
⇤ (r2àw2àY2) `P
(r2àÝàÝ) + Induc.
(r3àÝàÝ) ààà + Induc.
[ r k Y k p ] )⇤ G
[r2Y3r3] )⇤ w2 GG

CFGs and PDAs
CFGs and PDAs
Induc. Induc. Induc.
Proof of [qXp] ⇒ w ⇒ (q,w,X) ⊢ (p,ε,ε). (Induction on # of steps of derivation) GP
ó Basis: Let [qXp] ⇒∗ w in one step. Then, [qXp] −→ w must be a production rule. G
Consequently, (p,ε) ∈ (q,w,X) and (q,w,X) ⊢ (p,ε,ε). P
ó Induction: Let [qXp] ⇒∗ w. G
4 (r0àY1 àààYk) 2 Ü(qàaàX)
1 [qXp] ) a[r0Y1r1][r1Y2r2] ààà [rk1Ykp] ) w = aw1 àààwk
⇤⇤ (r0àw1àY1) `P (r1àÝàÝ) ⇤ (rk1àwkàYk) `P (pàÝàÝ)
(r1àw2àY2) `P (r2àÝàÝ)
(qàaw w àààw àX) ` (r àw àààw àY àààY ) ⇤ (r àw àààw àY àààY ) ⇤ ààà ⇤
() (qàaàX) `P (r0àÝàY1 àààYk) ⇤
1 2z k P 0 1 k 1 k `P 1 2 k 2 k `P `P (pàÝàÝ)
w Lemma 6.2.1 Lemma 6.2.1 Lemma 6.2.1

Deterministic PDAs
Deterministic PDAs (DPDAs)
ó PDAs are (by definition) non-deterministic.
ó Deterministic PDAs are defined to have no choice in their transitions.
Definition
A DPDA P is a PDA P = (Q,Σ,Γ,δ,q0,Z0,F) such that for each q ∈ Q and X ∈ Γ,
ó |δ(q,a,X)|≤1foranya∈Σ∪{ε},
i.e., a configuration cannot transition to more than one configuration.
ó |δ(q,a,X)|=1forsomea∈Σ⇒δ(q,ε,X)=∅,
i.e., both reading or not reading (a tape symbol) cannot be options.
ó DPDAs have a computation power that is strictly better than DFAs Example: L(P) = N(P) = {0n1n : n ≥ 1}
0à Z0=0Z0
P: q0 1à0=Ý q1
ó DPDAs have a computation power that is strictly worse that PDAs. (We will discuss this later)

Deterministic PDAs
Languages Accepted by DPDAs
ó The two notions of acceptance (empty stack and final state) are not equivalent in the case of DPDAs.
ó There are languages L such that L = L(P) for some DPDA P, but there exists no P′ such that L = N(P′).
Theorem 6.4.1
Every regular language L is the language accepted by the final states of some DPDA.
Simply view the DFA accepting L as a DPDA (with the stack always containing Z0).
ó The regular language L = {0}∗ cannot equal N(P) for any DPDA P.
ó Suppose DPDA P accepts L by emptying its stack. Since 0 is accepted, P
eventually reaches a configuration (p, ε, ε) for some state p.
Now, suppose that P is fed with the input 00. Since P is deterministic, P reads a 0 and eventually has to get to (p, ε, ε). However, it hangs at this configuration and cannot read any further input symbols. Hence, P cannot accept 00.

Deterministic PDAs
Languages Accepted by DPDAs
ó A language L is said to have the prefix property if no two distinct strings in the language are prefixes of one another.
Theorem 6.4.2
A language L = N(P) for some DPDA P iff L has the prefix property and L = L(P′′) for some DPDA P′′.
⇒ LetL=N(P)forsomeDPDAP. Letw,ww′ beinLwithw′ ̸=ε. Then ∗
(q0, w, Z0) ⊢ (p, ε, ε) for some p ∈ Q. The DPDA hangs at this state since the stack P
is empty. Hence, it cannot accept ww′. The fact that L = L(P′′) for some DPDA P′′
follows from Theorem 6.2.2 since the construction yields a deterministic PDA. ÝàX0=Ý
PDA P PDA P00
Ýà Z0à Z0X0

Deterministic PDAs
Languages Accepted by DPDAs
⇐ Let DPDA P′′ be given. Let w ∈ L(P′′), (q0,w,Z0) ⊢ (p,ε,γ) for some p ∈ F, and
γ ∈ Γ. Since L(P′′) satisfies the prefix property, the PDA cannot enter any final state before reading all of w.
ó Then we can delete all transitions from final states; this X ∈ Γ does not alter L(P′′). ó Then, the construction of Theorem 6.2.2 yields a deterministic PDA P′ such that
N(P′) = L(P′′) = L. PDA P00
Ýà any=Ý
Ýà Z0à Z0X0
Ýà any=Ý
Ýà any=Ý
Ýà any=Ý

Deterministic PDAs
DPDAs and Unambiguous Grammars
Theorem 6.4.3
If L = N(P) for some DPDA P, then L has an unambiguous CFG. Proof
ó Let G be the CFG constructed in Theorem 6.3.2.
ó Suppose G is ambiguous. Then, for some w ∈ L has 2 leftmost derivations.
ó However, each derivation corresponds to a unique trajectory of configurations in P that also accepts w by emptying stack.
ó Since P is deterministic, the trajectories, and hence, the derivations have to be identical. Hence, G is unambiguous.

Deterministic PDAs
DPDAs and unambiguous Grammars
Theorem 6.4.4
If L = L(P) for some DPDA P, then L has an unambiguous CFG.
ó Let $ be a symbol not in the alphabet of L.
ó Consider L′ = {w$ : w ∈ L}. Then, L′ has the prefix property.
ó By Theorem 6.4.2, there must exist a DPDA P′ such that L′ = N(P′).
ó By Theorem 6.4.3, L′ has an unambiguous CFG G′ = (V,T,P,S).
ó Define CFG G = (V ∪{$},T \{$},P ∪{$ −→ ε},S).
ó G generates L.
ó Suppose G is ambiguous. Then, for some w ∈ L has 2 leftmost derivations.
ó The last steps in the two leftmost derivations of w must use the production $ −→ ε.
ó Then, the portions of the two leftmost derivations without the last production step correspond to two leftmost derivations of w$.
ó Hence, G′ must be unambiguous, which is a contradiction. Hence, G is also unambiguous.

Additional Slides
Explanation for Slide 11
ó ⇒ Suppose we want to show that if there is a derivation in G generating w, then there is a trajectory in P accepting w. To do that let S ⇒∗ w.
ó Then there must be a LM derivation as in the left column. In each step of the leftmost derivation, a part of the string w is uncovered, and the uncovered part is succeeded by a non-terminal.
ó Let after i = 1,…,k − 2 production uses: (1) the prefix wi+1 of w be uncovered (shown in purple); (2) the leftmost non-terminal be Vi+1 (shown in orange); and (3) is the string to the right of the leftmost non-terminal αi+1 that contains both terminal and non-terminal symbols (shown in beige).
ó After the kth production rule, we have derived wk = w.
ó Now suppose S → γ1 = w2V2α2, V2 → γ2, …, Vk−1 → γk−1 be the k −1 production
rules used in the leftmost derivation.
ó Now let us show that a trajectory exists for P using the above information we have laid out.
ó Since there is only one state for the PDA, the right part of the slide presents only the portion of tape yet to be read, and the stack contents; additionally, it also gives the string of terminals that has been popped up until any point in time.
ó Initially, the tape contains w, the stack contains S, and ε has been popped thus far. 22/28

Additional Slides
Explanation for Slide 11 (Continued)
ó Now since S → γ1 is a valid production rule, by the definition of P, there is a Type-22 transition that reads nothing from the input tape, reads S from the stack and pushes γ1 := w2V2α2 onto the stack. Thus, the following one-step computation is valid
(q0, w, S) ⊢ (q0, w, w2V2α2). P
ó Note that w1 is the prefix of w uncovered after the first step of the derivation, and hence matches the first few symbols of w. Then, it is clear that one can perform |w| Type-1 transitions that pop each of these symbols from the stack. Thus, after popping |w1| symbols, we see that:
(q0 , w , S ) ⊢ (q0 , w , w2 V2 α2 ) ⊢ (q0 , w \ w2 , V2 α2 ), PP
where we let w \w2 to denote the suffix of w2 in w.
ó Now, note that V2 → γ2 is a valid production rule; hence, there is a valid one-step
computation from (q0, w \ w2, V2α2) that uses the corresponding Type-2 transition. The resultant configuration change will then be
(q0,w,S)⊢(q0,w,w2V2α2)⊢(q0,w\w2,V2α2)⊢(q0,w\w2,(w3 \w2)V3α3), PPP
where (w3 \ w2)V3α3 := γ2α2.

Additional Slides
Explanation for Slide 11 (Continued)
ó Again, we see that a portion of the top of the stack contains w \ w2, which matches the initial segment of the input tape. Then there is a valid multi-step computation involving |w3 \ w2| Type-1 transitions that pops w3 \ w2. The resultant configuration will then be q0, w \ w3, V3α3).
ó Now, this proceeds until all of w is exhausted (read) from the input tape, and the configuration at the end will be (q0,ε,ε). Since the stack is empty, the original string w will be accepted.
ó ⇐ The direction that a trajectory accepting w in P implies a derivation of w in G is simply arguing the above in the reverse direction using the facts that:
ó a trajectory for accepting w in P must consist only of Type-1 and Type-2 transitions, and each Type-2 transition corresponds to a unique production in G.
ó The argument is literally the same as above except that we now uncover the production rule from the corresponding Type-2 transition.

Additional Slides
Explanation for Slide 13
Inductive proof for (q, w , X ) ⊢ (p, ε, ε) ⇒ [qXp] ⇒ w based on length of computation. PG
ó Basis: Let (q,w,X) ⊢ (p,ε,ε) be a one-step computation. Thus, w has to be an P
input symbol or ε. Then, by definition of one-step computation it must be true that
(p,ε) ∈ (q,w,X). Then, by the construction of G, we have [qXr] → w (see Slide 12
for the construction), and hence [qXr] ⇒∗ w. G
ó Induction: (q,w,X) ⊢ (p,ε,ε) in say k > 1 steps. Let us assume that the in the first P
step of the computation, the symbol a is read from the input tape (or a = ε). Let
w = ax. Let’s break the k-step computation to a single step followed by a k − 1-step computation as detained in 1 (encircled in black). Let r1 be the state of the PDA after the first step and let X be popped and Y1 · · · Yk be pushed onto the stack after the first step/transition/move.
ó Now, the claim is that the k − 1 step portion of the computation can be expanded into the sequence of computations as given in 2 (encircled in black). The reasoning is as follows. The ID (r1, x, Y1 · · · Yk ) eventually changes to (p, ε, ε). There must be a finite number of moves after which the effective stack change is the popping of Y1, i.e., after a finite number of steps Y2 is at the top for the very first time. The steps until then could have popped Y1, pushed a string, and then popped it eventually to reveal Y2 at the top.

Additional Slides
Explanation for Slide 13 (Continued)
ó Let w1 be the portion of the input tape read and r2 be the state pf the PDA when this intermediate ID where Y2 is at the top of the stack (i.e., the stack contains Y2 ··· ,Yk) is attained. Thus,
(r,x,Y1 ···Yk) ⊢ (r2,x \ w1,Y2,···Yk) ⊢ (p,ε,ε), PP
whereagainweletw\w1 tobethesuffixofw1 inw.
ó By a similar argument, after reading another segment, say w2, of the input tape and
reaching (some) state r3, the top of the stack of the PDA contains Y3 for the very first time. Thus,
(r,x,Y1 ···Yk) ⊢ (r2,x \ w1,Y2,···Yk) ⊢ (r3,x \ (w1w2),Y3,···Yk) ⊢ (p,ε,ε). PPP
ó Proceeding inductively, we see that 2 (encircled in black) holds. Note that x is then equal to the concatenation of the wi’s, i.e., x = w1 ···wk.
ó Now focus on the computation within the blue block in 2. In no intermediate ID of the computation is Y2 at the top of the stack (since (r2,x \w1,Y2,···Yk) is the very first time Y2 is at the top of the stack). Thus, the stack contents Y2 · · · Yk are never visited in this first set of moves, and hence, we see that
(r1,x,Y1 ···Yk) ⊢ (r2,x \ w1,Y2,···Yk) ⇒ (r1,w1,Y1) ⊢ (r2,ε,ε). (3) PP

Additional Slides
Explanation for Slide 13 (Continued)
ó Similarly, we see that the in portion of the computation in orange, no intermediate ID of the computation has Y3 at the top of

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts