CS计算机代考程序代写 flex algorithm Slide 1

Slide 1

Pushdown Automata
Chapter 12

We need a device similar to an FSM except that it needs more power.

The insight: Precisely what it needs is a stack, which gives it an unlimited amount of memory with a restricted structure.

Example: Bal (the balanced parentheses language)

(((()))
Recognizing Context-Free Languages

Definition of a Pushdown Automaton
M = (K, , , , s, A), where:
K is a finite set of states
 is the input alphabet
 is the stack alphabet
s  K is the initial state
A  K is the set of accepting states, and
 is the transition relation. It is a finite subset of

(K  (  {})  *)  (K  *)

state input or  string state string of
to pop to push
from top on top
of stack of stack

Definition of a Pushdown Automaton
A configuration of M is an element of K  *  *.

The initial configuration of M is (s, w, ).

Yields
Let c    {}, 1, 2,   *, and w  *.

Then:
(q1, cw, 1) |-M (q2, w, 2) iff ((q1, c, 1), (q2, 2))  .

Let |-M* be the reflexive, transitive closure of |-M.

C1 yields configuration C2 iff C1 |-M* C2

Computations
A computation by M is a finite sequence of configurations C0, C1, …, Cn for some n  0 such that:

● C0 is an initial configuration,
● Cn is of the form (q, , ), for some state q  KM and
some string  in *, and
● C0 |-M C1 |-M C2 |-M … |-M Cn.

Nondeterminism
If M is in some configuration (q1, s, ) it is possible that:

●  contains exactly one transition that matches.

●  contains more than one transition that matches.

●  contains no transition that matches.

Accepting
A computation C of M is an accepting computation iff:

● C = (s, w, ) |-M* (q, , ), and (empty stack)
● q  A. (accepting state)

M accepts a string w iff at least one of its computations accepts.

Other paths may:
● Read all the input and halt in a nonaccepting state,
● Read all the input and halt in an accepting state with the stack not
empty,
● Loop forever and never finish reading the input, or
● Reach a dead end where no more input can be read.

The language accepted by M, denoted L(M), is the set of all strings accepted by M.

Rejecting
A computation C of M is a rejecting computation iff:

● C = (s, w, ) |-M* (q, w, ),
● C is not an accepting computation, and
● M has no moves that it can make from (q, w’, ).

M rejects a string w iff all of its computations reject.

So note that it is possible that, on input w, M neither accepts nor rejects.

A PDA for Balanced Parentheses
M = (K, , , , s, A), where:
K = {s} the states
 = { (, ) } the input alphabet
 = { ( } the stack alphabet
A = {s}
 contains:
((s, (, ¶), (s, ( ))
((s, ), ( ), (s, ))

¶ This does not mean that the stack is empty

A PDA for AnBn = {anbn: n  0}

M = (K, , , , s, A), where:
K = {s, f} the states
 = {a, b, c} the input alphabet
 = {a, b} the stack alphabet
A = {f} the accepting states
 contains: ((s, a, ), (s, a))
((s, b, ), (s, b))
((s, c, ), (f, ))
((f, a, a), (f, ))
((f, b, b), (f, ))
A PDA for {wcwR: w  {a, b}*}

A PDA for {anb2n: n  0}

A PDA for PalEven ={wwR: w  {a, b}*}
S  
S  aSa
S  bSb

A PDA:

A PDA for {w  {a, b}* : #a(w) = #b(w)}

Accepting Mismatches
L = {ambn : m  n; m, n > 0}

Start with the case where n = m:

a//a
b/a/
b/a/
● If stack and input are empty, halt and reject.

● If input is empty but stack is not (m > n) (accept):

● If stack is empty but input is not (m < n) (accept): 1 2 Accepting Mismatches L = {ambn : m  n; m, n > 0}

a//a
b/a/
b/a/
● If input is empty but stack is not (m > n) (accept):

a//a
b/a/
b/a/

/a/
/a/
1
2
2
1
3

Accepting Mismatches
L = {ambn : m  n; m, n > 0}

a//a
b/a/
b/a/
● If stack is empty but input is not (m < n) (accept): a//a b/a/ b/a/ 1 2 2 1 4 b// b// Putting It Together L = {ambn : m  n; m, n > 0}
● Jumping to the input clearing state 4:
Need to detect bottom of stack.

● Jumping to the stack clearing state 3:
Need to detect end of input.

AnBnCn vs AnBnCn
Consider AnBnCn = {anbncn: n  0}.

PDA for AnBnCn?

Now consider L = AnBnCn. L is the union of two languages:

1. {w  {a, b, c}* : the letters are out of order}, and

2. {aibjck: i, j, k  0 and (i  j or j  k)} (in other words,
unequal numbers of a’s, b’s, and c’s).

A PDA for L = AnBnCn

Are the Context-Free Languages Closed Under Complement?
AnBnCn is context free.
If the CF languages were closed under complement, then
AnBnCn = AnBnCn

would also be context-free.

But we will prove that it is not.

L = {anbmcp: n, m, p  0 and n  m or m  p}
S  NC /* n  m, then arbitrary c’s
S  QP /* arbitrary a’s, then p  m
N  A /* more a’s than b’s
N  B /* more b’s than a’s
A  a
A  aA
A  aAb
B  b
B  Bb
B  aBb
C   | cC /* add any number of c’s
P  B’ /* more b’s than c’s
P  C’ /* more c’s than b’s
B’  b
B’  bB’
B’  bB’c
C’  c | C’c
C’  C’c
C’  bC’c
Q   | aQ /* prefix with any number of a’s

PDAs and Context-Free Grammars
Theorem 12.3: The class of languages accepted by PDAs is exactly the class of context-free languages.

Recall: context-free languages are languages that
can be defined with context-free grammars.

Restate theorem:

Can describe with context-free grammar

Can accept by PDA

Going One Way
Theorem 12.1: Each context-free language is accepted by some PDA.

Proof (by construction) (not required for midterm !!)

The idea: Let the stack do the work.

Two approaches:

Top down

Bottom up

Top Down
The idea: Let the stack keep track of expectations.

Example: Arithmetic expressions

E  E + T
E  T
T  T  F
T  F
F  (E)
F  id

(1) (q, , E), (q, E+T) (7) (q, id, id), (q, )
(2) (q, , E), (q, T) (8) (q, (, ( ), (q, )
(3) (q, , T), (q, T*F) (9) (q, ), ) ), (q, )
(4) (q, , T), (q, F) (10) (q, +, +), (q, )
(5) (q, , F), (q, (E) ) (11) (q, , ), (q, )
(6) (q, , F), (q, id)

A Top-Down Parser
The construction in general:

M = ({p, q}, , V, , p, {q}), where  contains:
● The start-up transition ((p, , ), (q, S)).

● For each rule X  s1s2…sn. in R, the transition:
((q, , X), (q, s1s2…sn)).

● For each character c  , the transition:
((q, c, c), (q, )).

Example: L = {anb*an}
CF grammar:
(p, , ), (q, S) (q, , S), (q, ) S  
(q, a, a), (q, ) (q, , S), (q, B) S  B
(q, b, b), (q, ) (q, , S), (q, aSa) S  aSa
(q, , B), (q, ) B  
(q, , B), (q, bB) B  bB

input = a a b b a a

Trans state unread input stack
p a a b b a a 
0 q a a b b a a S
3 q a a b b a a aSa
6 q a b b a a Sa
3 q a b b a a aSaa
6 q b b a a Saa
2 q b b a a Baa
5 q b b a a bBaa
7 q b a a Baa
5 q b a a bBaa
7 q a a Baa
4 q a a aa
6 q a a
6 q  

Going The Other Way
Theorem 12.2: If a language is accepted by a pushdown automaton M, it is context-free (i.e., it can be described by a context-free grammar).

The proof is by construction – very complicated, not required !!

Nondeterminism, minimality
A PDA M is deterministic iff:
● M contains no pairs of transitions that compete with each other
● Whenever M is in an accepting configuration it has no available moves.

1. Determinism is strictly less powerful: There are context-free languages for which no deterministic PDA exists.

2. It is possible that a PDA may
● not halt,
● not ever finish reading its input.

3. There exists no algorithm to minimize a PDA. It is undecidable whether a PDA is minimal.