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.
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
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.