Assignment 18 - Post's Correspondence Problem

  1. Getting Started

    Please refer to this page for information on how to work on your assignment.

  2. Outline

    Post's correspondence problem consists of two arrays of words, the first array and the second array. Both arrays have the same length, but the words in it can be of different length. A correspondence is a list of indices which tell how to arrange the elements of the arrays such that both give the same word. Examples can be found in the last lecture, note that the indexing of arrays starts in JavaScript with 0.

    (a)   Position         (0)     (1)     (2)     (3)      (4)
          First Array      abb     a       bab     baba     aba
          Second Array     bbab    aa      ab      aa       a
          Correspondence 1  1, 0, 0,  3,   0,  4
          First word        a abb abb baba abb aba
          Second word       aa bbab bbab aa bbab a
          Correspondence 2  1, 0, 4
          First word        a abb aba
          Second word       aa bbab a
                            (Thanks to Ryan Flynn for finding this one)
    (b)   Position        (0)     (1)     (2)     (3)      (4)
          First Array     a       aa      aba     aabb     abb
          Second Array    b       ba      bba     bbba     bba
          No correspondence exists

    Since this problem is unsolvable, it is impossible to write an algorithm which checks the existence of a correspondence. Nevertheless, one can check whether there is a correspondence of a given length. This should be implemented in this exercise.

  3. What has to be done in detail

    The searchcorrespondence() function has to be implemented. It obtains three inputs: firstarray, secondarray and indexarray which are the parameters defining Post's correspondence problem and the array which will carry the correspondence. The length of this array is already given. The implementation should cover two aspects:

    One can use the printcorrespondence(firstarray, secondarray, indexarray) function to print the existing solutions and also analyze this function in order to get an idea of how to test for correspondences. The function to be edited is the subsearch() function which is called from correspondencesearch(). Here it comes with a parameter k which says that indexarray[k] is now the variable which has to be set. The subsearch() function should call itself with all possible values inserted at indexarray[k]. It means that for any possible choice h the following should be done:

    Furthermore, please optimize your solution. That is, do not make such a call if it can be eaisly seen that whatever will be done, it will not lead to a match. This optimization will speed up the processing of the search a lot.

JavaScript Starts Here.
JavaScript Ends Here.