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

Welcome to Scribd!

  • 36 views

    Pushdown Automata-PDA: Prof. (DR.) K.R. Chowdhary

    Uploaded by

    haine12345
    The document summarizes pushdown automata (PDA). It defines PDA as consisting of a finite set of states, an input tape, a pushdown stack, transition functions, and a start state. The transition function of a PDA allows it to manipulate the stack without reading input. The document provides examples of PDA that recognize the languages anbn and wcwR to illustrate how PDAs operate and are able to recognize context-free languages.

    Copyright:

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

    Pushdown Automata-PDA: Prof. (DR.) K.R. Chowdhary

    Uploaded by

    haine12345
    36 views7 pages
    The document summarizes pushdown automata (PDA). It defines PDA as consisting of a finite set of states, an input tape, a pushdown stack, transition functions, and a start state. The transition function of a PDA allows it to manipulate the stack without reading input. The document provides examples of PDA that recognize the languages anbn and wcwR to illustrate how PDAs operate and are able to recognize context-free languages.

    Original Description:

    Hjggh

    Original Title

    12-pda

    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 summarizes pushdown automata (PDA). It defines PDA as consisting of a finite set of states, an input tape, a pushdown stack, transition functions, and a start state. The transition function of a PDA allows it to manipulate the stack without reading input. The document provides examples of PDA that recognize the languages anbn and wcwR to illustrate how PDAs operate and are able to recognize context-free languages.

    Copyright:

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

    Pushdown Automata-PDA: Prof. (DR.) K.R. Chowdhary

    Uploaded by

    haine12345
    The document summarizes pushdown automata (PDA). It defines PDA as consisting of a finite set of states, an input tape, a pushdown stack, transition functions, and a start state. The transition function of a PDA allows it to manipulate the stack without reading input. The document provides examples of PDA that recognize the languages anbn and wcwR to illustrate how PDAs operate and are able to recognize context-free languages.

    Copyright:

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

    Pushdown Automata-PDA

    Prof. (Dr.) K.R. Chowdhary


    Email: kr.chowdhary@iitj.ac.in

    Formerly at department of Computer Science and Engineering


    MBM Engineering College, Jodhpur

    Saturday 25th February, 2017

    kr chowdhary TOC 1/ 7
    Introduction to Pushdown Automata (PDA)

    Definition
    A PDA consists: a infinite tape, a read head, set of states, and a start
    state. The additional components from FA are: Pushdown stack, initial
    symbol on stack, and stack alphabets (). PDA M = (Q, , , s, , Z0 ),
    where,
    Q is finite set of states,
    is finite set of terminal symbols (language alphabets),
    s start state (q0 ),
    is transition function: : Q ( { }) finite subset of
    Q .
    The transition function of a PDA is so defined, because a PDA may have
    transitions without any input read.

    kr chowdhary TOC 2/ 7
    Introduction to PDA
    The PDA has two types of storage; 1) infinite tape, just like the FA, 2)
    pushdown stack, is read-write memory of arbitrary size, with the
    restriction that it can be read or written at one end only.
    Input tape

    a a a b b b

    Readhead Direction of Read head movment

    pushdown stack

    finite
    control
    Z0

    Definition
    ID (Instantaneous Description) of a PDA is: ID : Q , start-id
    {q0 } {Z0}, e.g., start ID may be (q0 , ax, Z ).

    kr chowdhary TOC 3/ 7
    PDA Transitions
    (q, a, Z ) = finite subset of {(p1 , 1 ), (p2 , 2 ), . . . , (pm , m )}. Therefore,
    (pi , i ) (q, a, z)), for 1 i m.
    By default, a PDA is non-derministic machine. Due to this fact, a PDA
    can manipulate the stack without any input from tape. Following are
    some of the transitions in PDA:

    Case - I: A PDA currently in symbol , moves to state qj


    state qi , stack symbol A, with and write A on stack:
    input , moves to state qi and (qi , , ) = (qj , A).
    write on the stack:
    (qi , , A) = (qi , ).
    Case - II: A PDA currently in , A| , |A
    state qi , with input, and
    stack symbol , moves to qi qi
    state qi , and writes A on Case-I Case II
    stack: (qi , , ) = (qi , A).
    Case - III: A PDA in state qi , qi
    , |A
    qj
    Case III
    reads input , with stack

    kr chowdhary TOC 4/ 7
    Language recognition: an b n
    A move of a PDA is defined as (q, ax, Z ) M (q , x, ), if
    (q , ) (q, a, Z ). (In Z , Z is top symbol on stack)
    Example
    Construct a PDA to recognize L = {an b n |n 0}.

    Solution: The transition function, (q0 , aabb, Z0 ) (q0 , abb, AZ0 )


    moves, and PDA are shown below. (q0 , bb, AAZ0 )
    M = (Q, , , s, F , , Z0 ) (q1 , b, AZ0 )
    = {a, b} (q2 , , Z0 ),
    Q = {q0 , q1 , q2 }, F = {q2 } the PDA halts and accepts.
    (q0 , , ) = (q2 , )
    (q0 , a, ) = (q0 , A)
    a, |A b, A|
    (q0 , b, A) = (q1 , ) b, A|
    q0 q1
    (q1 , b, A) = (q1 , )
    , | q2 , |
    (q1 , , ) = (q2 , ) ;accept
    kr chowdhary TOC 5/ 7
    Language Recognition: wcw R

    Example
    Construct a PDA to recognize L = {wcw R |w {a, b}}.

    Solution: Transition function, (q0 , c, ) = (q1 , )


    moves, and PDA:
    (q1 , , Z0 ) = (q2 , Z0 ) ;accept
    M = (Q, , , s, F , , Z0 )
    = {a, b, c}, d {a, b}, (q0 , aabcbaa, Z0 )
    (q2 , , Z0 )
    Q = {q0 , q1 , q2 }, F = {q2 },
    = {a, b, Z0 }
    1. (q0 , c, Z0 ) = (q2 , Z0 ) ; accept d, |d d, d|
    with w = w R =
    q0 , | q1
    , / q2
    2. (q0 , d, Z0 ) = (q0 , dZ0 )
    (q0 , d, ) = (q0 , d )
    c, /
    (q1 , d, d) = (q1 , )

    kr chowdhary TOC 6/ 7
    PDA moves

    PDA moves
    1. (q, x, ) (q , , ) (q, xy , ) (q , y , )
    2. (q, xy , ) (q , y , ) (q, xy , ) (q , y , )
    The case 1., above is obvious, however, the case 2., is not
    guaranteed due to the trace of computation shown below.


    b b

    b
    b b

    b
    b
    b

    stack

    time

    kr chowdhary TOC 7/ 7

    You might also like