{\rtf1\ansi \deff4\deflang1033{\fonttbl{\f1\froman\fcharset2\fprq2 Symbol;}{\f4\froman\fcharset0\fprq2 Times New Roman;}{\f15\fnil\fcharset2\fprq2 Wingdings;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;
\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;
\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\widctlpar \f4\fs20 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext15 header;}{
\s16\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext16 footer;}{\*\cs17 \additive\sbasedon10 page number;}}{\info
{\title Consider: we will now define an instantaneous description (ID) for a PDA, so that we can more easily show its operation (or, in this case, show that we understand the operation of a given PDA)}{\author Sharon M. Tuttle}{\operator Sharon M. Tuttle}
{\creatim\yr2000\mo2\dy12\hr7\min4}{\revtim\yr2000\mo2\dy12\hr19\min44}{\version5}{\edmins49}{\nofpages3}{\nofwords542}{\nofchars3091}{\*\company CNRS - HSU}{\vern57431}}\widowctrl\ftnbj\aenddoc\formshade \fet0\sectd \linex0\endnhere {\header \pard\plain 
\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 CIS 480 - More on PDA's
\par p. {\field{\*\fldinst {\cs17  PAGE }}{\fldrslt {\cs17\lang1024 1}}}
\par }{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}{\*\pnseclvl5
\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8\pnlcltr\pnstart1\pnindent720\pnhang
{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \qc\widctlpar \f4\fs20 {\b\fs24 MORE on PDA's}{\fs24 
\par }\pard \widctlpar {\fs24 
\par }\pard \widctlpar {\fs24 Consider: we will now define an }{\b\fs24 instantaneous description }{\fs24 (ID) for a PDA, so that we can more easily show its operation (or, in this case, show that we understand the operation of a given PDA).
\par }\pard \widctlpar {\fs24 
\par The current state of a PDA could be given as:
\par \tab (current state, remaining input to be handled, stack contents)
\par where
\par \tab remaining input's first symbol is assumed to be the one currently being "pointed"  
\par             at, 
\par and
\par \tab stack contents are assumed to be written so stack top is on the left;
\par 
\par }\pard \widctlpar {\fs24 You could then "trace" the action of a PDA as a series of ID's in this form, say separated by |--, as so:
\par }\pard \widctlpar {\fs24 
\par FIRST: Consider the PDA M discussed in Sipser and in lecture: 
\par 
\par }\pard \widctlpar {\fs24 M = (\{q1, q2, q3, q4\}, \{0, 1\}, \{$, 0, 1\},  }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , q1, \{q4\}) where
\par }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  is defined as follows:
\par }{\b\fs24 \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q1, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol"
 \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (q2, $) \}}{\b\fs24 
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q2, 0, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings"
 \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (q2, 0) \}
\par }{\b\fs24 \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q2, 1, 0) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (q3, }{\fs24 {\field{\*\fldinst SYMBOL
 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) \}
\par }{\b\fs24 \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q3, 1, 0) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (q3, }{\fs24 {\field{\*\fldinst SYMBOL
 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) \}
\par }{\b\fs24 \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q3, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , $) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f 
"Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (q4, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) \}
\par }\pard \widctlpar {\fs24  \tab (...and all others are undefined)
\par 
\par So, let's consider the operation of this PDA on the string 000111, using PDA ID's.
\par 
\par initial ID:\tab (q1, 000111, empty)
\par 
\par (q1, 000111, empty) |-- (q2, 000111, $)\tab (in state q1, without seeing an input, push a 
\par                                                                         $ onto the stack without first popping the 
\par                                                                         stack) 
\par \tab \tab \tab \tab \tab \tab (in state q2, when input 0, push a 0 onto 
\par }\pard \fi720\li3600\widctlpar {\fs24 stack without first popping the stack)
\par }\pard \widctlpar {\fs24                                   |-- (q2, 00111, 0$)\tab (in state q2, when input 0, push a 0 onto 
\par }\pard \fi720\li3600\widctlpar {\fs24 stack without first popping the stack)
\par }\pard \widctlpar {\fs24                                   |-- (q2, 0111, 00$)\tab (ditto)
\par                                   |-- (q2, 111, 000$)\tab (in state q2, when input 1, when pop the 
\par }\pard \fi720\li3600\widctlpar {\fs24 stack and see a 0 --- go to state q3 and
\par }\pard \widctlpar {\fs24 \tab \tab \tab \tab \tab \tab do not push onto the stack
\par                                   |-- (q3, 11, 00$)\tab \tab (in state q3, when input 1, when pop the 
\par }\pard \fi720\li3600\widctlpar {\fs24 stack and see a 0 --- stay in state q3 and do 
\par not do not push onto the stack
\par }\pard \widctlpar {\fs24 
\par                                   |-- (q3, 1, 0$)\tab \tab (in state q3, when input 1, when pop the 
\par }\pard \fi720\li3600\widctlpar {\fs24 stack and see a 0 --- stay in state q3 and do 
\par not do not push onto the stack
\par }\pard \widctlpar {\fs24                                   |-- (q3, empty, $)\tab (in state q3, without seeing any input, when 
\par }\pard \fi720\li3600\widctlpar {\fs24 pop the stack and see a $ --- go to state q4 
\par and don't push anything onto the stack
\par }\pard \widctlpar {\fs24                                  |-- (q4, empty, empty)
\par }\pard \widctlpar {\fs24 ...and, since we have exhausted all the input and are in a final state, the string 000111 has been accepted by this PDA M.    
\par }\pard \widctlpar {\fs24 
\par }{\b\fs24 SECOND EXAMPLE:
\par }{\fs24 Consider the language \{wcw}{\fs24\super R}{\fs24  | w is in (0 + 1)*\}. Here is a PDA that accepts it:}{\b\fs24 
\par 
\par }\pard \widctlpar {\fs24 M = (\{q0, preC, postC, q3\}, \{0, 1, c\}, \{$, 0, 1, c\},  }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , q0, \{q3\}) where
\par }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  is defined as follows:
\par 
\par }{\b\fs24 \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (q0, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol"
 \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (preC, $) \}}{\b\fs24 
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (preC, 0, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings"
 \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (preC, 0)\}\tab }{\b\fs24  
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (preC, 1, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings"
 \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (preC, 1)\}\tab }{\b\fs24  
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (preC, c, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 ) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings"
 \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (postC, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  )\}\tab }{\b\fs24  
\par 
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (postC, 0, 0) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (postC, }{\fs24 {\field{\*\fldinst SYMBOL
 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  )\}}{\b\fs24  
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (postC, 1, 1) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings" \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (postC, }{\fs24 {\field{\*\fldinst SYMBOL
 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  )\}}{\b\fs24  
\par \tab }{\fs24 {\field{\*\fldinst SYMBOL 100 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 (postC, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24 , $) }{\fs24\lang1024 {\field{\*\fldinst SYMBOL 224 \\f "Wingdings"
 \\s 12}{\fldrslt\f15\fs24}}}{\fs24  \{ (p3, }{\fs24 {\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 12}{\fldrslt\f1\fs24}}}{\fs24  )\}\tab 
\par }\pard \widctlpar {\fs24 
\par Consider the PDA ID's as this PDA processes the string 110c011:
\par 
\par (q0, 110c011, empty)\tab |-- (preC, 110c011, $)\tab |-- (preC, 10c011, 1$)\tab |-- (preC, 0c011, 11$)
\par \tab \tab \tab |-- (preC, c011, 011$)\tab |-- (postC, 011, 011$)\tab |-- (postC, 11, 11$)
\par \tab \tab \tab |-- (postC, 1, 1$)\tab |-- (postC, empty, $)\tab |-- (p3, empty, empty)
\par }\pard \widctlpar {\fs24 ...and, since we have exhausted all the input and are in a final state, the string 110c011 has been accepted by this PDA M.
\par }\pard \widctlpar {\fs24 \tab 
\par }{\b\fs24 WHAT might I ask on a test in this area?
\par }\pard \widctlpar {\fs24 *   I might give a formal description of a PDA, and ask for a series of PDA ID's showing that some string is or is not accepted (to see if you understand PDA operation);
\par }\pard \widctlpar {\fs24 *   I might give a formal description of a PDA, and an ID for some point in the processing of a string, and ask for the ID that would next result (to see if you understand PDA operation);}{\b\fs24 
\par }\pard \widctlpar {\b\fs24 
\par }\pard \widctlpar {\b\fs24 
\par 
\par }\pard \widctlpar {\fs24 
\par 
\par }}