0
$\begingroup$

I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$ are regular languages, I also know that $L$ is regular $\implies L^{c}$ is regular .

It is easy to generalize in this manner:

Let $L_{1},...L_{n}$ be regular languages and $x\in\{0,1\}^{n}$ a vector, then $L_{1}^{x_{1}}\cap...\cap L_{n}^{x_{n}}, L_{1}^{x_{1}}\cup...\cup L_{n}^{x_{n}}$ is regular, where $L^{0}$ denotes $L^{c}$ and $L^{1}$ denotes $L$, I can also generalize by changing some of the $\cap$ to $\cup$ .

My question is: How can this be generalized ?

It seems that both statements have some kind of Boolean operations in the scene that given $L_{1},...,L_{n}$ I can represent those languages with binary vectors (I also noted that $A\cup B=(A^{c}\cap B^{c})^{c}$ so the two generalizations I gave seem to be the equivalent to each other)

  • 0
    @MarkDominus - just a notation because I used binary vectors...2012-08-11

1 Answers 1

2

As you noted, regular languages are closed under arbitrary finite Boolean operations, which gives the following easy corollary:

Given $n$ regular languages $L_1 , \ldots , L_n$ and any function $f : \mathcal{P} ( \{ 1 , \ldots , n \} ) \to \{ 0 , 1 \}$ the language $L$ given by $w \in L$ iff $f ( \{ i \leq n : w \in L_i \} ) = 1$ is also regular.

(To see this, note -- using the notation in the OP -- that all languages of the form $L_1^{x_1} \cap \cdots \cap L_n^{x_n}$, where the $x_i$ are in $\{0,1\}$, are regular. Given $f$ as above, let $( x_{1,1} , \ldots , x_{1,n} )$, $\ldots$, $( x_{k,1} , \ldots , x_{k,n} )$ enumerate the $n$-tuples in the pre-image of $1$. Then the language in question is $\bigcup_{j=1}^k ( L_1^{x_{j,1}} \cap \cdots \cap L_n^{x_{j,n}} ),$ which is regular, being a finite union of regular languages.)

Without going into other operations (concatenation, Kleene-star, etc.), I'm not certain if anything more general can be said.

  • 0
    Very very ni$c$e!2012-08-11