Semi-decide Post's Correspondence Problem The Post's Correspondence Problem (PCP) gives you a list of pairs of strings, P_1 ... P_n. Your task is to find a k, and some sequence of k indices such that fst(P_i1) ... fst(P_ik) = snd(P_i1) ... snd(P_ik)

We're trying to find some sequence of the pairs where the word we build from the first part is equal to the word on the second part.
A solution can use any of the pairs any number of times, and in any order.

For example, if our pairs are (0,110), (11,1) and (001,100) , then one solution is the world 11001110, with the solution sequence of 2321:

11 001 11 0
1  100 1  110


Some will have no solution, such as (001, 01), (0001, 01).

Input:

An arbitrary number of words, separated by spaces.
Each word is of the format seq1,seq2 where each seq1 and seq2 are strings consisting only of 0 or 1, of arbitrary length.

Example: the above examples would have the following formats:

0,110 11,1 001,110

001,01 0001,01


Output:

If there is some sequence of the pairs which solves the PCP, output the word of the solution, followed by a space, followed by the sequence. The pairs are numbered starting at 1.

If there is no such sequence, run forever. (The problem is undecidable, so this will have to do).

Example output

11001110 2321

# second example never halts


Hint:

This is Turing Complete, so you're going to have to use some sort of infinite search.
Python 3, 223 216 199 192 191 189 183 bytes
Thanks to @KarlKastor for pointing out that I could use count
from itertools import*
j=''.join
def f(x):
 for l in count(1):
  for i in product(x,repeat=l):
   *b,=zip(*i);c=j(b[0])
   if c==j(b[1]):print(c,j(str(x.index(k)+1)for k in i));return

A function that takes input of a tuple of pairs of strings x in the form ((seq1,seq2),(seq1,seq2)...) and prints the output to STDOUT in the same format as the test cases.
To continuously output solutions rather than just one solution, remove the return statement.
How it works
The function generates all l-length arrangements of the string pairs using product, with l being initialised at 1. This list is then unpacked and transposed using zip; this leaves a two-element list, where the first element contains all the first strings in the pairs, and the second all the second strings in the pairs. Each element is concatenated to a string using join; if these are the same, we have a hit and the string is printed to STDOUT. The sequence of pair indices is then generated by looking up each pair in the original arrangement using index; these indices are concatenated to a string, and also printed to STDOUT. If no solution exists for that l, l is incremented and the process repeated.
Try it on Ideone