Turing Machines

 

    A Turing Machine Program has three components.

1.      Alphabet

This is the set of symbols used in instructions which may or

may not be the same as the alphabet of inputs/output strings.

2.      An infinite tape: 2-way infinite

3.      An unordered set of instructions.

There are different versions of instructions such as

      Quadruples (default) and

      Quintuples.

 

Quadruple Turing Machines have three quadruple instructions:

            Qi        Sj         Sk        Ql        // Rewrite the current tape square (Print Quad)

            Qi        Sj         R         Ql        // Move to Right

            Qi        Sj         L         Ql        // Move to Left

    

Turing Machine Programs operate based upon

            The Current state and

            The Current tape symbol.

 

EX:     

            A = {1}

            Quadruples:

                        Q1       B         R         Q2

                        Q2       1          R         Q2

                        Q2       B         1          Q3

                        Q3       1          R         Q3

                        Q3       B         1          Q1       // “Q1  1” is the terminating   

                                                                        // combination.

 

            This program computes f(x) = x+2, not strictly

 

            The following program computes the same function Strictly:

 

                        Q1       B         R         Q2

                        Q2       1          R         Q2

                        Q2       B         1          Q3

                        Q3       1          R         Q3

                        Q3       B         1          Q4

                        Q4       1          L         Q4

                        Q4       B         B         Q5       “Q5  B” is the terminating combination

 

THM:

Any TM (program) can be converted into an equivalent Quintuple TM (program)

 

            Quintuple TMs have the following two quintuple instructions:

            1.         Qi  Sj  Sk  R  Ql

            2.         Qi  Sj  Sk  L  Ql

 

            Quintuple-1: If the given current state and the given

current tape symbol together match, then a (possibly) new

symbol will be printed into the

            current tape square before moving to the right.   

            Quintuple-2: Similar except that the move is to the left.

 

 

            EX:

           

            Q1       B         R         Q2       // just one quintuple needed

            Q2       a          R         Q2       // just one quintuple needed

            Q2       b          R         Q2       // just one quintuple needed

            Q2       B         c          Q3       // many quintuples needed due to

                                                            // unwanted move, R-move.

            Q2       c          c          Q2       // many quintuples needed

 

            Equivalent Quintuple TM:

 

            Q1       B         B         R         Q2

            Q2       a          a          R         Q2

            Q2       b          b          R         Q2

            Q2       B         c          R         Q6       // unwanted R-move

            Q6       B         B         L         Q3       // Undo R-move

            Q6       a          a          L         Q3       // Undo R-move

            Q6       b          b          L         Q3       // Undo R-move

            Q6       c          c          L         Q3       // Undo R-move

            Q2       c          c          R         Q5       // unwanted R-move

            Q5       B         B         L         Q2

            Q5       a          a          L         Q2

            Q5       b          b          L         Q2

            Q5       c          c          L         Q2

 

 

A Universal Turing Machine                                  

 

Just as we had a Universal function and a Universal program, it is rather straightforward to think of a Universal Turing Machine as a TM that is equivalent to a Universal program, as an immediate consequence of above Corollary that equivalences all

Turing machines and all PC functions and all Programs in L (The numeric-processing SIMPLE Language)

 

TM as an acceptor of a language

 

In addition to computing PC functions, another capacity of TM’s is in accepting a certain language which is a (possibly infinite) set of strings on a certain alphabet.

 

            1. An alphabet, A,  out of which strings are to be formed.

                This same alphabet can be considered as that of a TM.

            2. We say that a string x (in A^* ) is accepted by a TM if and only if this

                TM stops after starting with the initial tape configuration with the

    string x included as the input string.

3. Given a TM, M, the language accepted by this TM, denoted by,         

     L(M).

                 L(M) = {x | x is accepted by this TM}                            

 

            EX:     A = {a,b}

Q1       B         R         Q2

                        Q2       a          a          Q3

                        Q2       B         B         Q2       // infinite loop not to accept

// the l.

                        Q2       b          b          Q2       // infinite loop not to accept a

                                                                        // string

                                                                        // starting with a ‘b’

Q3       a          R         Q3

                        Q3       B         B         Q3       // infinite loop not to accept a

// string

                                                                        // consisting only of ‘a’’s

                        Q3       b          b          Q4

                        Q4       b          R         Q4

                        Q4       a          a          Q4       // “Q4 B” is the terminating

// combination           

           

                        NOTE: L(M) = a⁺ b⁺

 

                        The computation of this TM is given below when the

 input string is “aabbb”:

 

                        ...BBB Q₁ BaabbbBBB...                  ->

                        ...BBBB Q₂ aabbbBBB...                  ->

                        ...BBBBa Q₃ abbbBBB...                  ->

                        ...BBBBaa Q₃ bbbBBB...                  ->

                        ...BBBBaab Q₄ bbBBB...                  ->

                        ...BBBBaabb Q₄ bBBB...                  ->

                        ...BBBBaabbb Q₄ BBB...                  ->

           

Each above is called an I.D., instantaneous description that clearly

describes the computation so far done up to a certain point in time..

           

Equivalence of TM’s and RE sets

 

THM 3.1

A language is accepted by a TM if and only if it is RE.

            Proof:

            1. Suppose that a language L is accepted by a TM, M.

                Let f(x) be the PC function computed by this TM.

                L = L(M) = { x | f(x) is defined }

                So, L is RE.

            2. Suppose that a language L is RE.

                Then, there is a PC function f(x) such that L = { x | f(x) is defined }  

                This PC function must be computed by a TM say M.

                Then L = L(M). So, it is accepted by a TM.

            QED.

 

NOTE:                      

Any language L consisting only of strings of ‘1’’s can be considered as a

set of numbers and it is RE if and only if it is accepted by a TM.                       

 

TM Halting problem

 

Just as the Halting problem (for programs) is unsolvable, TM Halting problem is unsolvable as programs and TM’s are equivalent.

THM4.1 says just a little bit more than that.

    

There is a TM with alphabet {1} that has an unsolvable halting problem.

 

     Proof:

     Let S be an RE language on {1} that is not recursive.

     And, let a TM M be such that  L(M) = S.

     Then, the halting problem of this TM is unsolvable as if it were solvable

     then S would be recursive.

 

Reduction of a problem to another problem.

 

Often, we can use an unsolvable problem in showing that another problem is also unsolvable. In this case we can use a reduction method.

           

Definition of Problem Reduction

Given two problems A and B, we say that A is reduced to B if and only if every possible instance of problem A is transformed into an instance of problem B so that by solving the latter instance ( of B) we can solve the former instance (of A).

 

NOTE:

1. When A is reduced to B, all possible instances of A are covered but not all

     instances of problem B.

2. The problem B is at least as hard as problem A.

    So, if problem A is unsolvable then so is problem B as if B were solvable

    then A would be solvable.

 

EX: TM State Problem                                                                    

  

Given a TM and an input string and a state of this TM, the problem of deciding whether this TM ever enters the given state on taking the given input string.

 

Given a TM, M1, on alphabet {1}, we can construct another TM M2 on the same alphabet as follows:

Assume that the last state of M1 is Q_k        

1. M2 will have all the quadruples of M1 and in addition it will have

            2. a quadruple of the form:  Qi Sj Sj Q_k+1 

                for every combination of Qi and Sj that M1 does not have

                where Qi is one of the states of M1,

               Sj is either B or ‘1’ and

                           Q_k+1   is a state that M1 does not have.

           

Now, we have just reduced the M1 halting problem to the M2 State problem for the state Q_k+1  of M2.

That is, if we can solve the problem of deciding whether or not TM M2 ever

enters the state  Q_k+1  then we would be solvable the Halting problem of M1.

 

Since the Halting problem of arbitrary TM is unsolvable, the State Problem of arbitrary TM is unsolvable as this particular TM’s State Problem is unsolvable.

 

Nondeterministic TM (NDTM) and deterministic TM (DTM)

 

A Deterministic TM is a TM that does not have two quadruples with the same combination of the current state and the current tape symbol.

And, a nonterministic TM is any TM with no such restriction. That is, a nondeterministic TM may or may not have two quadruples starting with the same two components (of the current state and the current tape symbol).   

So, A DTM is just a special case of a NDTM.

 

            EX:     A = {a,b}

Q1  B  R  Q2  // this quad and the next one make

// the TM truly nondet.

                        Q1  B  R  Q3 

                        Q2  a   B  Q3

                        Q3  B  R  Q3

                        Q3  a    B  Q4 // Q4 = at least one ‘a’ erased.

                        Q4   B  R  Q4

                        Q4   a   R  Q4

                        Q4   b   R  Q5 // Q5 = at least one ‘b’ found

                        Q4   c   c   Q4  // input string has a ‘c’

                        Q5   b   R  Q5

                        Q5   B  L   Q6 // Q6 = rightend of remaining input substring.

                        Q6   b   B  Q7 // Q7 = one ‘b’ erased (rightmost one)

                        Q7  B  L   Q8  // Q8 = remaining substring must be empty or right

                        Q8  b   L  Q9  // Q9 = remaining substring has at least one ‘b’

                        Q9  b  L   Q9

                        Q9  a   a   Q3  // Leftmost remaining ‘a’ found.

                        Q9  B  B  Q9   // input string has more ‘b’’s than ‘a’’s

                        Q8  a   a   Q8  // input string has more ‘a’’s than ‘b’’s

                        Q3  b   b   Q3  // input string starts with a ‘b’ or has more ‘b’’s

                        Q2  b   b   Q2 // input string starts with a ‘b’

                        Q2  B  B  Q2   // input string empty

                        Q5  a   a   Q5  // input string has ‘a’ after ‘b’’s

 

                        “Q8 B” is the accepting terminating condition.                 

                        L is supposed to be: L =  {a^m b^m   +  a^m+1 b^m | m>=1}                   

  

 

Equivalence among many versions of TM

 

  1.  Quadruple TM’s

  2.  Quintuple TM’s

  3.  One-Way infinite tape TM’s

  4.  Nondeterministic TM’s

 

  The equivalence of the first two has already been established.

  The equivalence between DTM’s and NDTM’s is involved:

            1. Conversion from DTM to NDTM is trivial.

            2. Conversion from NDTM to DTM is involved.

                We will examine this in the next chapter.

 

  The equivalence between TM’s with one-way infinite tape and those

  with two-way infinite tape.

            1. Conversion from the former to latter is trivial.

            2. Conversion from the latter to the former is involved a little bit.

 

Major steps involved in simulating a two-way infinite tape TM M1 by a one-way infinite tape TM M2.

Key idea:

Regard a two-way  infinite tape as being “hinged” so it can be folded to become a one-way infinite tape  with two tracks, an upper track and a lower track.

1. Let the alphabet of M1 be A = {S1,S2, ..., Sn} and its states be {Q1,Q2, ...,  

    Qk} and we assume that it computes a unary function f(x).

2. Just as M1 starts with the initial I.D. of: 

             ...BBBB Q1 B X BBB...       where X is the input string.

                M2 will start with the initial I.D. of:

                 # Q1 B X BBB...   where ‘#’ is a special symbol to mark the

                                       leftend of one-way infinite tape for most of the computation.

3. The alphabet of M2 will be:  

            A + {#} + {b ⁱ _j    | 0 <= i,j <= n} where  b ⁱ _j  represents two symbols

                        S_i on the upper track and  S_j  on the lower track.

4. The states of M2 will be:

            {Q1, Q2, Q3, Q4, Q5} + {P_i  , R_i    | 1<=i<=K}

and some additional states.

5. M2 quadruples are made up of three sections:

                        BEGINNING

                        MIDDLE

                        ENDING       

6. BEGINNING

    To copy the input of M1 on the upper track putting blanks on the correspondng

     lower track of each square occupied by the input string.

    This section will have the following quadruples:

                        Q1  B  R  Q2

                        Q2  Si  R  Q2  // for 1 <= i <= n

                        Q2  B  L  Q3

                        Q3  Si   Sⁱ ₀  Q3           // for 0 <= i <= n

                        Q3  Sⁱ ₀  L  Q3 // for 0 <= i <= n

                        Q3  #   R  P1

     This section turns the initial I.D. from

                        ...BBB # Q1 B S2 S1 S3 BBB...    to

                        # P1  b²₀    b¹₀  b³₀  BBB ...

 

7.  MIDDLE

     This section will have quadruples corresponding to those of M1 plus some

      more for switchover between the upper and the lower tracks and also for

      turning the original blanks into modified blanks when necessary.

                 a.    Qi  Sj  Sk  Ql              Pi b^j _m   b^k _m   Pl                      // 0<=m<=n

                                                            Ri b^m _j   b^m _k   Rl                     // 0<=m<=n

                 b.    Qi  Sj   R  Ql               Pi  b^j _m   R   Pl                        // 0<=m<=n

                                                            Ri  b^m _j    L   Rl                       // 0<=m<=n

                 c.    Qi  Sj   L  Ql               Pi  b^j _m   L   Pl             // 0<=m<=n

                                                            Ri  b^m _j    R   Rl                       // 0<=m<=n

                 d.     Additions                  Pi  B    b⁰₀    Pi                         // 1 <= i <= K

                                                            Ri  B    b⁰₀    Ri                        // 1 <= i <= K

                                                            Pi  #     R    Ri                         // 1 <= i <= K

                                                            Ri  #     R     Pi                         // 1 <= i <= K

8.  ENDING

     This section will have quadruples needed for converting the output strings

     in the modified alphabet into equivalent strings in the original alphabet of M1.

     To begin with, it has the following quadruples:

     a.     For each combination, Qi Sj, which no quadruple of M1 contains:

                        Pi  b^j _m   b^j_m   Q4                     // 0 <= m <= n

                        Ri  b^m_j   b^m_j   Q4                     // 0 <= m <= n

     b.                Q4   b^m_k   L   Q4                     // 0 <= m,k <= n

                        Q4   #      B   Q5                     // 0 <= m,k <= n

 

     c.     Above parts of this section is to produce the following I.D.:

 

                        B  Q5   bⁱ¹_j1  bⁱ²_j2  ... b ^ik_jk  BBB ...

 

     The remaining task of this section is to convert above I.D. into

      a tape contents of:

                        S_jk S_jk-1 S_{jk -2  ,...,} S_j1  S _i1 S _i2  ,..., S _ik

 

 

CFL (Context-Free Languages)

 

Context-Free Grammars:

  A production of the form:  N ->  w

                   where N must be exactly one non-terminal symbol (and nothing

                   else) and  w  consists of zero or more grammar symbols (possibly

                   zero symbol)

 

Example:    CFG1

 

          ‘S’ is the Start Symbol.

          S -> S R

          S -> R

          R -> ( )

          R -> ( S )

 

          We call a production-rule “Empty” if its RHS is an empty-string.

          Above CFG has no such production rule, namely, there is no empty

          production rule.

 

          Consider the following CFG:

 

          S -> S R                                   S ->  R P

          S -> R                                      S ->  R

          R -> ( )                                     P ->  S

          R -> ( P )                                 P ->  l

          P ->  S                                     R -> ( )

          P ->  l                                      R -> ( S )

 

          Each of above two CF grammars generates the same language as the

          above grammar, CFG1, does but they each has an empty production rule.

 

Elimination of Empty Production rules from a CFG.

 

Unless the Start Symbol can derive the empty-string, each empty production can be eliminated from a CFG without altering the language defined by the grammar. And, if the Start Symbol can derive the empty string then the only empty production we are unable to eliminate from a CFG must be the one for that Start Symbol which we can consider to be a special case of the empty rule.

 

          Example: CFG2

          S -> S P

          S -> Q P Q

          P -> ( )

          P -> ( S )

          Q -> R

          R -> S R

          R - > l

 

          In the above grammar, we say that ‘R’ and ‘Q’ are each “Nullable”

          as each of them can derive the empty string as the former does it directly by

          itself while the latter does it indirectly by way of ‘R’.   

          But, other non-terminals are not nullable.

          After eliminating the only one empty rule of the grammar, we may

          obtain the following equivalent grammar:

 

          S -> S P

          S -> Q P Q

          S -> Q P

          S -> P Q

          S -> P

          P -> ( )

          P -> ( S )

          Q -> R

          R -> S R

          R -> S

 

          Note that ‘S’ is not nullable in the above CFG2, so the resulting CFG

          has no empty rule at all,  not even ‘S ->  l‘  

          Also, note that we can systematically eliminate all “Unit” production

          rules of the form: N ->  RHS where RHS string consists only of one

          non-terminal and no terminal such as “R -> S” and “Q -> R”

 

 

Definition: CF Languages.

 

A language generated by any CFG is Context-Free.

 

Two normal forms:

 

1. Chomsky Normal Form

          Each rule is of the form except possibly for “S -> l “:

                   N -> P Q               // RHS has exactly two non-terminals

                   N -> t                             // RHS has just one terminal symbol

 

2. Greibach Normal Form

          The RHS of each rule starts with a terminal followed by zero or

          more nonterminals except possibly for “S -> l “

 

THM:

Any CFL without the empty string can be generated by a CFG either in the CNF or in the GNF.

That is, any CFG whose defined CFL does not include the empty string can be converted into an equivalent CFG in either the CNF or

the GNF.

 

Converting into equivalent GNF is involved though. It requires eliminating all left-recursive rules such as:

          N -> N Alpha    or                   N -> M Beta

                                                M -> N Gamma.

 

Pumping Lemma (CFL): Necessary condition for CFL.

 

Let L be an infinite CFL. Then there is a positive integer m such that for all (sufficiently long) strings z in L with |z| >=m, z can be written in the form z =uvwxy, where the following properties hold:

                   |vx| >= 1,

                   |vwx| <= m, and

                   uv^k w x^ky is in L for all k>=0.

 

This lemma can be used to show that a certain language in question is not a CFL instead of showing that it is as the Lemma is only a necessary condition for CFL’s and satisfying the lemma by a language does not assure that the language is indeed a CFL.

 

Example:

          Consider the CFL defined the CFG1 above.

          This language has strings such as: (), ()(), (()), ()()(), ()(()), (())(),

          (()()), ((())), and so forth.

 

          We can take ((())) for a sufficiently long string, z, and decompose

          this string into five parts such that:

                   u = “(“

                   v = “(“

                   w = “()”

                   x = “)”

                   y = “)”

          Then we see that following strings we can pump each is in this language:

                   (())              // when k=0

                   ((()))            // when k=1

                   (((())))          // when k=2

                   ((((()))))       // when k=3

                   (((((())))))     // when k=4  and so forth.

         

 

Acceptors: NPDA(Non-deterministic Pushdown Automata)

  

An NPDA is a 7-tuple: (Q,  S, S,  d, Q1, S0, F)

where Q is a finite set of states,  

            S is a finite set of Input symbols,

            S is a finite set of Stack symbols,

            d is a finite set of transitions (or moves),

            Q1 is the Initial state,

            S0 is the Start stack symbol, and

            F is a finite state of zero or more Final (or Accepting) states.

 

Acceptance conditions:

1.              The entire input string must be scanned in only one direction.

The NPDA must scan each input symbol just once while moving

the input string from left to right.

That is, each input symbol is said to be “Consumed” when it is used in deciding the next move by the NPDA. Once consumed, an input symbol is never to be used again in deciding the next move. 

2.              At the time of scanning the input string in its entirety, either

a.       the stack must be empty (Acceptance by Empty-Stack) or

b.      the NPDA must enter one of the accepting states so designated

(Acceptance by Final-States) 

3.              The NPDA stops when there is no move defined for the combination of

a.       the current state

b.      the current stack symbol and

c.       the current input symbol.

4.               An input string is rejected

a.       when the NPDA does not stop at all or

b.      when the NPDA stops in one of non-accepting states in case of Acceptance by Final-States or without the stack being completely empty in case of Acceptance by Empty-Stack, or

c.       when the NPDA stops before scanning the entire input string.

 

EX:      An NPDA accepting L = {wcw^R  | w in (0+1)^*} by Empty-Stack.

            R is the Start stack symbol.

            (Q1, 0, R)  ->  (Q1, XR)         (Q1, 1, R)  ->  (Q1, YR)

            (Q1, 0, X)  ->  (Q1, XX)         (Q1, 1, X)  ->  (Q1, YX)

            (Q1, 0, Y)  ->  (Q1, XY)         (Q1, 1, Y)  ->  (Q1, YY)

            (Q1, c, R)  ->   (Q2,  R)

            (Q1, c, X)  -> (Q2,  X)

            (Q1, c, Y)  -> (Q2,  Y)

            (Q2, 0, X)  -> (Q2,  l)           (Q2, 1, Y)  -> (Q2,  l)                      

            (Q2, l, R)  -> (Q2,  l)           // NPDA can make this move for any input

symbol without consuming it or when no input symbol is left.

 

            Suppose that input string is: 011c110

            The NPDA will have the following sequence of moves:

                        (Q1, 011c110, R)                    ->

                        (Q1,   11c110, XR)                 ->

                        (Q1,     1c110, YXR)              ->

                        (Q1,       c110, YYXR)           ->

                        (Q2,         110, YYXR)           ->

                        (Q2,           10, YXR)              ->

                        (Q2,             0, XR)                 ->

                        (Q2,              l, R)                   ->

                        (Q2,              l, l)                   // Terminal I.D. shows an empty stack and

                                                                        an empty input string.

 

            Note that “011c1100” will not be accepted as the stack will become empty but

            the input is not to be entirely scanned. And, each time the stack becomes empty                 the NPDA has to stop as there is no move defined for an empty stack.

 

            Also note the above NPDA is deterministic because

(1)   there is at most one move defined for any combination of a state, an input

      (non-empty) symbols and a stack symbol and

(2)   for any move, m, defined using an empty input symbol, there is no other

move defined for the state and the stack symbol used in that move m.

      For example, an NPDA with the following two moves defined will be

      non-deterministic:

            either   (Qi,  Sj,  Pk)  -> (Ql, XXX)

                        (Qi,  Sj,  Pk)  -> (Qu, ???)

            or         (Qi,  Sj,  Pk)  -> (Qv, ???)

                        (Qi,   l,  Pk)  -> (Qw, ???)

 

            Another example:

An NPDA accepting L = {ww^R  | w in (0+1)⁺} by Empty-Stack

 

            R is the Start stack symbol.

            (Q1, 0, R)  ->  (Q1, XR)         (Q1, 1, R)  ->  (Q1, YR)

            (Q1, 0, X)  ->  (Q1, XX)         (Q1, 1, X)  ->  (Q1, YX)

            (Q1, 0, Y)  ->  (Q1, XY)         (Q1, 1, Y)  ->  (Q1, YY)

            (Q1, 0, X)  -> (Q2,  l)           (Q1, 1, Y)  -> (Q2,  l) 

// For above two moves, current input symbol is assumed to be beginning

// of the second half.

            (Q2, 0, X)  -> (Q2,  l)           (Q2, 1, Y)  -> (Q2,  l)                      

            (Q2, l, R)  -> (Q2,  l)          

 

            Note that above NPDA is really non-deterministic.

            Let us consider possible sequences of moves when input string is:

                        011110

 

            a.  A successful sequence

                        (Q1, 011110, R)          ->

                        (Q1, 11110, XR)         ->

                        (Q1, 1110, YXR)        ->

                        (Q1, 110, YYXR)       ->

                        (Q2, 10, YXR)                        ->

                        (Q2, 0, XR)                 ->

                        (Q2, l, R)                    ->

                        (Q2, l, l)

 

            b. An unsuccessful sequence

                        (Q1, 011110, R)          ->

                        (Q1, 11110, XR)         ->

                        (Q1, 1110, YXR)        ->

                        (Q1, 110, YYXR)       ->

                        (Q1, 10, YYYXR)      ->

                        (Q2, 0, YYXR)           No next move defined, so stopping in failure.

 

c. Another unsuccessful sequence

(Q1, 011110, R)          ->

                        (Q1, 11110, XR)         ->

                        (Q1, 1110, YXR)        ->

(Q2, 110, XR)             No next move defined, so stopping in failure.

 

 

Equivalence of two Acceptance Conditions:

            Acceptance by Empty-Stack and

            Acceptance by Final-States.

 

THM:

If L is L(M2) for some NPDA M2, then L is N(M1) for some NPDA M1.

   Note that L(M) denotes the language accepted by M by Final-States and

   N(M) denotes the language accepted by M by Empty-Stack.

 

Proof:

We need to construct M1 from M2 so that it will accept the same language

accepted by M2 but by Empty-stack.

Some key ideas for doing that:

1.              M1 will erase all remaining stack symbols as soon as M2 enters a final state

after doing the same things as M2 does.

2.              We need to prevent M1 from accidentally emptying the stack just because M2 does without entering a final state. For this, M1 will use a special bottom-of-stack symbol that M2 does not have.

This stack symbol will become its own Start stack symbol, Z₀ .

3.              M1 will need two extra states:

Q’  : Its own Initial state

Q_e  : A state in which M1 will just empty the stack.

 

Now, we are ready to assemble all needed transitions for M1.

          Assume that Q1 is the initial state of M2 and  S₀  is its Start stack symbol.

1.         (Q’,  l, Z₀)      -> (Q1, S₀ Z₀)

2.                  All existing transitions of M2.

3.                  (q,  l, Z)          -> (Q_e  , l)       for each accepting state q of M2 and each

stack symbol Z of M2 including Z₀       

4.                  (Q_e , l, Z)        -> (Q_e  , l)       for all stack symbols of M2 including Z₀  

 

From the construction, M1 should accept an input string by Empty-stack if and only if M2 accepts it by Final-States.

 

THM:

If L is N(M1) for some NPDA M1, then L is L(M2) for some NPDA M2.

 

Proof: Amounts to showing how we can construct M2 from a given M1.

Some key ideas for this construction:

1.                  M2 will need its own bottom-of-stack symbol that M1 does not have so that while simulating M1 encountering this bottom-of-stack symbol will initiating the process of entering the final state of M2 that M1 does not have.

2.                  M2 will use 2 extra states and one extra stack symbol:

Q_f  :  The only final state

Q₀  :  Its own initial state

Z₀  :   Its own bottom-of-stack symbol

 

The moves of M2 include:

       Assume that Q₁  and  S₀   are the initial state and the Start stack symbol of

       M1, respectively.

       1.              (Q₀ ,  l,  Z₀)     ->         (Q₁ , S₀ Z₀ )

       2.              All existing transitions of M1

       3.              (q,     l,  Z₀)     ->         (Q_f  , l)   for every state q of M1

 

From the construction, M2 will accept an input string by entering its only final state Q_f    if and only if M1 accepts by Empty-stack.

QED.

 

THM: (Equivalence of NPDA’s and CFL’s)

If L is a CFL, then there exists an NPDA M such that L = N(M)

Proof:

Use GNF CFG assuming that the CFL under consideration does not have the empty-string.

 

 

DCFL

            CFL’s that are accepted by a deterministic PDA, respectively.

            These are models for programming languages in actual use.

 

            Closure properties.

 

            Closed under

1.      Complementation

2.      MAX

3.      MIN

4.      inverse Homomorphism

5.      intersection with a regular set.

 

Not closed under

1.      Union

2.      Intersection

3.      Concatenation

4.      Reflexive closure

 

For Union, consider:

L1 = {0 ^j  1^j  2^k  |  j,k>=0}

L2 = {0 ^j  1^k  2^k  |  j,k>=0}

Each is a DCFL.

But, their union is a CFL but not DCFL.

L = Complement(L1+L2)

L3 = L ^ 0^* 1^* 2^*

                 = {0 ⁱ  1^j  2^k  | i<>j and j<>k}, which is not CFL

            Hence, L is not CFL. And, so L is not a DCFL.

            So, their union is not a DCFL.