Scribd Logo
Upload

Welcome to Scribd!

  • 7 views

    PDA1

    Uploaded by

    علي عبد الحمزه
    Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

    Copyright:

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

    PDA1

    Uploaded by

    علي عبد الحمزه
    7 views7 pages
    Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    7 views7 pages

    PDA1

    Uploaded by

    علي عبد الحمزه
    Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

    Copyright:

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

    Pushdown Automata

    Automata for Context-Free Languages


    Language class Syntax/Grammar Automata
    Regular regular expressions, DFA, NFA, NFAλ
    regular grammar
    Context-free context-free grammar ?

    • DFA, NFA, NFAλ: finite states = finite memory, e.g.


    – even or odd number of a’s read: two states even, odd
    – the last 2 letters read: four states for aa, ab, ba, bb.
    • Problem: languages like {anb n | n ≥ 0} need unbounded memory. A DFA with k
    states can only “count to k”.
    • Solution: extend FSA by adding memory
    • Automata for Context-Free Languages

    • Various simple memory models are possible:

    • Queue: First in, first out (like waiting in line)


    • Stack: Last in, first out (like a laundry basket)
    Stack Memory
    A stack can be described as a word over the stack alphabet Γ:

    • Empty stack is λ.

    • push(X, YZZY ) = XYZZY , push a new element on top (note top=left).

    • pop(YZZY ) = ZZY , remove the top element.

    • top(YZZY ) = Y , look at the top element.

    Note: the empty stack has no top.

     In PDA the stack holds a special symbol Z0 that indicates the bottom of the stack.
    Pushdown Automaton
    Formally, a pushdown automaton is a nondeterministic machine defined
    by the 7-tuple (Q, Σ, Γ, δ, q0, Z0, F), where
    ,Q is a finite set of states -
    - Σ is an input alphabet ,
    - Γ is the stack alphabet of symbols that can be pushed on the stack,
    δ : Q × Σε × Γε → P(Q × Γ*) is the transition function, where no tuple is -
    ,mapped to an infinite set
    - q0 ∈ Q is the start state,
    - Z0 ∈ Γ is the stack start symbol, and
    - F ⊆ Q is the set of accepting states.
    NOTES
    ● The automaton accepts if it ends in an accepting state with no
    input remaining.
    ● The language of a PDA is the set of strings that the PDA accepts:
    L(P) = { w ∈ Σ* | P accepts w }
    ● If P is a PDA where L(P) = L, we say that P recognizes L.
    Input symbol Top of stack Stack operations
    Push or Pop

    (a , Z0 ̸ a Z0 )

    You might also like