Condition to terminate BFS

Question

I have this assignment where given a list of tuples where each tuple contains 2 Strings like this :

• [ ("...","...") , ("...","...") , ("...","...") ... ]

I have to calculate the shortest path which will lead to an extreme-string.

An extreme-string is defined as a tuple of 2 strings where the first string is equal to the second string.

I know this might sound confusing so let me set an example.

Given :

• The list [("0","100") , ("01","00") , ("110","11")]
• With indices 0,1,2
• The shortest path is : [2,1,2,0]
• The extreme-string is equal to : "110011100"

Step by step explanation :

• Starting with tuple of index 2 the initial string is : "110","11"
• Appending tuple of index 1 next string is : "11001","1100"
• Appending tuple of index 2 next string is : "11001110","110011"
• Appending tuple of index 0 final string is : "110011100","110011100"

So say you begin with tuple ("X","Y") and then you pick tuple ("A","B") then result is ("XA","YB").

The way I approached this problem was using BFS which I already implemented and sounds right to me but there is an issue I am dealing with.

If the input is something like :

• [("1","111")]

then the algorithm will never terminate as it will always be in the state "111..." - "111111111..." .

Checking for this specific input is not a good idea as there many inputs that can reproduce this result.

Having an upper bound for the iterations is also not a good idea because in some cases a finite result may actually exist after the iterations bound.

Any insight would be really useful.

Answer 1

Problem described is semidecidable