Scribd Logo
Upload

Welcome to Scribd!

  • 49 views

    Department of Computer Science Assignment#02 Name: Zainab Zehra Sec:'C'

    Uploaded by

    Xyeda Sara
    The document is an assignment for a Theory of Automata course that includes questions about pushdown automata (PDA). It provides definitions and explanations of PDA, including that PDA can recognize context free languages using a stack to remember an infinite amount of information, unlike finite automata which have finite memory. PDA are defined by a set of states, input symbols, stack symbols, an initial state, initial stack symbol, set of final states, and a transition function.

    Copyright:

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

    Department of Computer Science Assignment#02 Name: Zainab Zehra Sec:'C'

    Uploaded by

    Xyeda Sara
    49 views3 pages
    The document is an assignment for a Theory of Automata course that includes questions about pushdown automata (PDA). It provides definitions and explanations of PDA, including that PDA can recognize context free languages using a stack to remember an infinite amount of information, unlike finite automata which have finite memory. PDA are defined by a set of states, input symbols, stack symbols, an initial state, initial stack symbol, set of final states, and a transition function.

    Original Title

    TOA-Assignment 2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is an assignment for a Theory of Automata course that includes questions about pushdown automata (PDA). It provides definitions and explanations of PDA, including that PDA can recognize context free languages using a stack to remember an infinite amount of information, unlike finite automata which have finite memory. PDA are defined by a set of states, input symbols, stack symbols, an initial state, initial stack symbol, set of final states, and a transition function.

    Copyright:

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

    Department of Computer Science Assignment#02 Name: Zainab Zehra Sec:'C'

    Uploaded by

    Xyeda Sara
    The document is an assignment for a Theory of Automata course that includes questions about pushdown automata (PDA). It provides definitions and explanations of PDA, including that PDA can recognize context free languages using a stack to remember an infinite amount of information, unlike finite automata which have finite memory. PDA are defined by a set of states, input symbols, stack symbols, an initial state, initial stack symbol, set of final states, and a transition function.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    DEPARTMENT OF COMPUTER SCIENCE

    Assignment#02

    NAME: ZAINAB ZEHRA SEC:’C’


    Course Title : Theory of Automata Total marks : 10

    Class : BS-6 Last date of submission: 10.3.2021 (9AM)

    Question.1:

    (a) What do you comprehend from the term Push Down Automata (PDA).
    A pushdown automaton is a way to implement a context-free grammar in a similar way
    we design DFA for a regular grammar. A DFA can remember a finite amount of
    information, but a PDA can remember an infinite amount of information.

    (b) Give formal definition of PDA.


    Pushdown Automata is a finite automata with extra memory called stack which
    helps Pushdown automata to recognize Context Free Languages.

    A Pushdown Automata (PDA) can be defined as :


    ● Q is the set of states
    ● ∑is the set of input symbols
    ● Γ is the set of pushdown symbols (which can be pushed and popped
    from stack)
    ● q0 is the initial state
    ● Z is the initial pushdown symbol (which is initially present in stack)
    ● F is the set of final states
    ● δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a
    given state, PDA will read input symbol and stack symbol (top of the
    stack) and move to a new state and change the symbol of stack.

    (c) Mention the components of PDA.


    A pushdown automaton has three components −
    ● an input tape,
    ● a control unit, and
    ● a stack with infinite size.
    The stack head scans the top symbol of the stack.
    A stack does two operations −
    ● Push − a new symbol is added at the top.
    ● Pop − the top symbol is read and removed.
    A PDA may or may not read an input symbol, but it has to read the top of the stack in
    every transition.

    (d) Give an example showing the construction of PDA.

    (f) How Push Down Automata differ from the Finite State Automata.

    1 For Type-2 grammar we can design For Type-3 grammar we can


    . pushdown automata. design finite automata.
    Non – Deterministic pushdown Non-Deterministic Finite
    2
    automata has more powerful than Automata has same powers as
    .
    Deterministic pushdown automata. in Deterministic Finite Automata.

    Not every Non-Deterministic Every Non-Deterministic Finite


    3 pushdown automata is transformed Automata is transformed into an
    . into its equivalent Deterministic equivalent Deterministic Finite
    pushdown Automata . Automata

    4 Context free languages can be Regular languages can be


    . recognized by pushdown automata. recognized by finite automata.

    Pushdown automata has the


    5 Finite Automata doesn’t has any
    additional stack for storing long
    . space to store input alphabets.
    sequence of alphabets.

    It gives acceptance of input


    6 It accepts the input alphabets by
    alphabhets by going up to empty
    . going up to final states.
    stack and final states.

    You might also like