Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one.

For example, say I have $N=3$, regular expression $c^*ab^*$ for rows and $b^*ac^*$ for columns. A solution would be

$\qquad\displaystyle\begin{pmatrix} a & b & b \\ c & a & b \\ c & c & a \end{pmatrix}$

I'm trying to find an algorithm that is faster than the brute force one. I am further looking for a way to split this algorithm in independent processes so I can use parallelism to decrease the time needed to reach a solution.

• Since language described by regex might have infinite number of words, I suspect you either work with only finite language OR you only list some first words generated by regex ordered in someway. It would be good to clarify on that. – Apiwat Chantawibul Feb 28 '15 at 20:51
• @D.W. Better now, isn't it? – Raphael Mar 4 '15 at 7:34
• One simple approach might be to express this as an instance of SAT and apply a SAT solver. There's no reason to expect this to work well for large $N$, but it's so easy to try you could try implementing it and see how well it works. – D.W. Mar 4 '15 at 19:13

Here's one idea that may still take exponential time in $N$ but is polynomial in the (length of) the regular expressions.
Consider strings over the shared alphabet $\Sigma$ of length $N^2$; each such string represents an $N \times N$ matrix stored row-wise. We insert a separation character $\$ \not\in \Sigma$between rows. We will now construct a finite automaton the accepts exactly the set of such strings that fulfill your two regular expressions. Let$r$resp.$c$be the row resp. column regular expression 1. Clearly,$r_N = (r \cap \Sigma^N\$)^{N-1}(r \cap \Sigma^N)$ matches all matrices that match $r$ in every row. Transform $r_N$ into an NFA $A_{r,N}$.
2. Denote with $A^{(i)}_{c,N}$ the automaton that matches only every $N$-th input symbol (ignoring $\$$) against$c$, starting with the$i$-th. I will leave the construction as an exercise; suffice to say that we need at most$N$copies of$A_c$. Now,$A_{c,N} = A^{(1)}_{c,N} \cap \dots A^{(N)}_{c,N}$accepts the set of all matrices each column of which matches$c$. 3. The automaton$A_{r,c,N} = A_{r,N} \cap A_{c,N}$accepts all the matrices you want. 4. A simple graph traversal finds an accepting path in$A_{r,c,N}$finds a solution matrix, if any. The blowup in size is mild (i.e. at most a factor$N^2$) for all constructions but the intersections; these multiply sizes, so we may look at a factor$2^N$for automaton size. That's still way better than checking all$\Sigma^{N^2}\$ possible matrices.