2.2 Pushdown Automata

图示2.11 2.12:PDA = FA + stack

deterministic PDA跟nondeterministic PDA不等价了,PDA指后者。


A pushdown automaton is a 6-tuple (Q,Σ,Γ,σ,q0,F)(Q,\Sigma,\Gamma,\sigma,q_0,F), where QQ, Σ\Sigma, Γ\Gamma, and FF are all finite sets, and

  1. QQ is the set of states,
  2. Σ\Sigma is the input alphabet,
  3. Γ\Gamma is the stack alphabet,
  4. σ:Q×Σϵ×ΓϵP(Q×Γϵ)\sigma:Q\times \Sigma_\epsilon \times\Gamma_\epsilon\rightarrow P(Q\times \Gamma_\epsilon) is the transition function
  5. q0Qq_0\in Q is the start state, and
  6. FQF\subseteq Q is the set of accept states.
定义(PDA's computation )

A pushdown automaton M=(Q,Σ,Γ,σ,q0,F)M=(Q,\Sigma,\Gamma,\sigma,q_0,F) computes as follows. It accepts input ww if ww can be written as w=w1w2...wmw=w_1w_2...w_m (where wiΣϵw_i\in\Sigma_\epsilon), and sequences of states r0,r1,...,rmr_0,r_1,...,r_m(where wiQw_i\in Q), and strings s0,s1,...,sms_0,s_1,...,s_m (其中siΓs_i\in\Gamma^*) exists that satisfy the following three conditions. The string sis_i represent the sequence of stack contents that MM has on the accepting branch of the computation.


定理2.20(L(PDA) = L(CFG))

A language is context free if and only if some pushdown automaton recognizes it.


推论2.32(regular languages \subset context free languages)

Every regular language is context free

证明方法:每个regular language都有一个能识别它的FA,而FA是PDA结构简化版,即FAs\subseteqPDAs,因此 regular languages\subseteqL(PDA)=regular languages



results matching ""

    No results matching ""