Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Pushdown Automata (PDA) : Reading: Chapter 6

    Uploaded by

    Saad Ahmed Sazan
    PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Pushdown Automata (PDA) : Reading: Chapter 6

    Uploaded by

    Saad Ahmed Sazan
    42 views9 pages
    PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

    Original Description:

    Original Title

    chapter-6

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    42 views9 pages

    Pushdown Automata (PDA) : Reading: Chapter 6

    Uploaded by

    Saad Ahmed Sazan
    PDA is a type of automaton that recognizes context-free languages by using a stack. A PDA has states, input symbols, stack symbols, transition functions, an initial state, initial stack symbol, and accepting states. The transition function specifies state transitions and stack operations based on the current state, input symbol, and top of stack symbol. For a given CFL, a PDA can be constructed with a transition diagram that grows the stack to represent the generated string and then pops the stack to check for a matching reverse string.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 9

    Pushdown Automata (PDA)

    Reading: Chapter 6

    1
    PDA - the automata for CFLs
    ■ What is?
    ■ FA to Reg Lang, PDA is to CFL
    ■ PDA == [ ε -NFA + “a stack” ]
    ■ Why a stack?

    Input ε-NFA Accept/reject


    string

    A stack filled with “stack symbols”


    2
    Pushdown Automata -
    Definition
    ■ A PDA P := ( Q,∑,Γ, δ,q0,Z0,F ):
    ■ Q: states of the ε-NFA
    ■ ∑: input alphabet
    ■ Γ: stack symbols
    ■ δ: transition function
    ■ q 0: start state
    ■ Z 0: Initial stack top symbol
    ■ F: Final/accepting states

    3
    old state input symb. Stack top new state(s) new Stack top(s)

    δ: Q x ∑ x Γ => Q x
    Γ
    δ : The Transition Function
    δ(q,a,X) = {(p,Y), …}
    1. state transition from q to p
    2. a is the next input symbol a X Y
    3. X is the current stack top symbol q p
    No

    Y is the replacement for X;


    n

    4.
    - d

    it is in Γ* (a string of stack
    e

    Y=? Action
    te

    symbols)
    m r

    i. Set Y = ε for: Pop(X) i) Y=ε Pop(X)


    i ni

    If Y=X: stack top is unchanged


    sm

    ii.
    ii) Y=X Pop(X)
    iii. If Y=Z1Z2…Zk: X is popped
    and is replaced by Y in Push(X)
    reverse order (i.e., Z1 will be iii) Y=Z1Z2..Zk Pop(X)
    the new stack top) Push(Zk)
    Push(Zk-1)
    …
    Push(Z2)
    Push(Z1)

    4
    Example
    Let Lwwr = {wwR | w is in (0+1)*}
    ■ CFG for L : S==> 0S0 | 1S1 | ε
    wwr
    ■ PDA for L :
    wwr
    ■ P := ( Q,∑, Γ, δ,q ,Z ,F )
    0 0

    = ( {q0, q1, q2},{0,1},{0,1,Z0},δ,q0,Z0,{q2})

    5
    Initial state of the PDA:

    Stack q0

    PDA for Lwwr top Z0

    1. δ(q0,0, Z0)={(q0,0Z0)}
    First symbol push on stack
    2. δ(q0,1, Z0)={(q0,1Z0)}

    3. δ(q0,0, 0)={(q0,00)}
    4. δ(q0,0, 1)={(q0,01)}
    5. δ(q0,1, 0)={(q0,10)} Grow the stack by pushing
    6. δ(q0,1, 1)={(q0,11)} new symbols on top of old
    (w-part)
    7. δ(q0, ε, 0)={(q1, 0)}
    8. δ(q0, ε, 1)={(q1, 1)} Switch to popping mode, nondeterministically
    9. δ(q0, ε, Z0)={(q1, Z0)}
    (boundary between w and wR)
    10. δ(q1,0, 0)={(q1, ε)}
    11. δ(q1,1, 1)={(q1, ε)} Shrink the stack by popping matching
    symbols (wR-part)
    12. δ(q1, ε, Z0)={(q2, Z0)}
    Enter acceptance state
    6
    PDA as a state diagram
    δ(qi,a, X)={(qj,Y)}

    Next Current Stack


    input stack Top
    Current symbol top Replacement
    state (w/ string Y)

    a, X / Y Next
    q q
    state
    i j

    7
    PDA for Lwwr: Transition Diagram

    Grow stack ∑ = {0, 1}


    0, Z0/0Z0 Γ= {Z0, 0, 1}
    1, Z0/1Z0 Pop stack for Q = {q0,q1,q2}
    0, 0/00
    0, 1/01
    matching symbols
    1, 0/10 0, 0/ ε
    1, 1/11 1, 1/ ε

    q q q
    ε, Z0/Z0
    0 ε, Z0/Z0 1 ε, Z0/Z0 2
    ε, 0/0
    ε, 1/1 Go to acceptance
    Switch to
    popping mode

    This would be a non-deterministic PDA 8


    Summary
    ■ PDAs for CFLs and CFGs
    ■ Non-deterministic
    ■ PDA acceptance types
    1. By final state
    2. By empty stack
    ■ PDA
    ■ Transition diagram

    You might also like