# Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this:

[atom_0] atom_1 (atom_2 | atorm_3 | ... | atom_n-1) <var> [atom_n]


Or any other combination of the following:

[], means, that the atom inside of it can be omitted
(), one of the atoms (seperated by | (stands for OR)) inside the braces can be chosen
<>, variable.
atom, it can be thought as a constant, which is hard coded.


For example:

The [yellow] (dog | cat) named <animalName>


This expression describes the following set of strings:

The yellow dog named <animalName>;
The yellow cat named <animalName>;
The dog named <animalName>;
The cat named <animal Name>;


The strings can vary, depending on the variable <animalName>, but say, we have two names for <variableName> : Petsy and Rony, then w'll have:

The yellow dog named Petsy;
The yellow cat named Petsy;
The dog named Petsy;
The cat named Petsy;
The yellow dog named Rony;
The yellow cat named Rony;
The dog named Rony;
The cat named Rony;


Right now, I'm thinking that I could build a tree (or graph) from the expression and then a DFS or BFS can do the job.

There is a standard construction for converting regular expressions into finite automata (check here or any textbook on formal languages). Once you have such an automaton in hand (either NFA or DFA) you can enumerate all accepted strings with a breadth-first search from the initial state looking for finite states (ordered by length).

Be careful, though: in general, regular expressions specify infinite languages. You can easily specify a length limit, though.

• Thank you, @Raphael. It seems that an automatan representation of the grammar will suit my goals. – user15992 Mar 23 '14 at 8:34

For regular expressions specified the way you describe, you can use a backtracking algorithm to enumerate all acceptable strings. Following is a Python implementation.

The input is a list of items. An item being one of the ones you describe.

gen_candidates generates candidates for the k'th position.

def gen_candidates(item):
c = []
if type(item) is list:
for e in item: c.append(e)
if(len(item) == 1):
c.append('')
elif type(item) is str:
c.append(item)
return c


The next function prints a solution when one is found.

def process_solution(solution):
s = ''
for e in solution:
if len(e) > 0:
s += e + ' '
print(s)


backtrack tries all possibilities recursively.

def backtrack(regex, solution, k):
if len(regex) > 0:
candidates = gen_candidates(regex[0])
for c in candidates:
solution[k] = c
backtrack(regex[1:], solution, k + 1)
else:
process_solution(solution)


You invoke the algorithm as follows:

input = ['The', ['yellow'], ['dog', 'cat'], 'named', '<animalName>']
solution = ['', '', '', '', '']
backtrack(input, solution, 0)

• Thank you, for your answer @saadtaame. I did some digging and I found that this kind grammar is called speech recognition grammar, however it turns out that there is a nice way to represent it in xml format. Further, I don't know python very well, but it seems to me, that you tread the constructions [atom1 | atom2 | ... | atomN] and (atom1 | atom2 | ... | atomN) as equally like and this is not suitable for me. Thank you again, for your answer and the time you spent on it ( : – user15992 Mar 23 '14 at 8:24