PPT Slide

Definition 5.1.3: for PDA M = (S, _______, s0, Z, R) we define the run-step relation for IDs as follows: ID directly leads to ID , written  _— , provided _____ {_}, X__, and (s', _)__(s, _, X).

Definition 5.1.4: for PDA M we define the run relation for IDs I and J, written I _—* J, if there exist IDs K0, K1, … , Kn (n�0) so that I=K0, J=Kn, and Ki _— Ki+1 for 0Ši

Definition 5.1.5: for PDA M we define

the language recognized by final state as L(M) = {w__* | _—* for some r_R and ___*},

and the language recognized by empty stack as Null(M) = {w__* | _—* for some s_S}.

Previous slide

Next slide

Back to first slide

View graphic version