[Solved]: Generating all strings that a regular expressions describe

Problem Detail: 

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.

Any comments or document/article references would be helpful to me.

Asked By : user15992

Answered By : Raphael

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.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents