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
    How would you want this generalised? Note that the next step up the "Boolean hierarchy" would be to consider infinite (let's start with countable) unions/intersections of regular languages. Clearly, these may not be regular, as the example in [this question](http://math.stackexchange.com/q/181230/8348) shows.2012-08-11
  • 0
    @ArthurFischer - I don't know exactly how to say this, but I want to use that with negation and conjunction I can express every boolean function2012-08-11
  • 0
    Why do you denote $L^C$ by $L^0$? $L^0$ should be $\{\epsilon\}$.2012-08-11
  • 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
    This is what I wanted, thank you. How can we prove this corollary ? (it is intuitive, but I can't really argue that...)2012-08-11
  • 0
    @Belgi: See the addition to my answer.2012-08-11
  • 0
    Very very nice!2012-08-11