[Solved]: Enumerate All Possible Strings Over Alphabet

Problem Detail: 

I am given the following decision problem:

A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $\Pi$ terminates on any input. Does there exist a pair ($I_1,I_2$) of strings such that $\Pi$ terminates on ($I_1,I_2$) with output value $true$?

It is clear that $\Pi$ is semi-decidable and to proof this, I am asked to give a semi-decision procedure. However, how do I enumerate all possible pairs strings? Or how do I enumerate all possbile (single) strings in general? Of course, such a program may never terminate, but that is no problem because I am only asking for semi-decidability.

EDIT2: Solution (Java)

Asked By : r0f1

Answered By : David Richerby

Consider a string over $\Sigma$ to be a number written in base $|\Sigma|$ and implement a counter. Remember to include leading "zeroes": first generate all the length-1 strings, then all the length-2 ones, and so on.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29841

3.2K people like this

 Download Related Notes/Documents