0
$\begingroup$

Is the intersection of a finite language $L_1$ and an infinite language $L_2$ always a regular language?

I've tried a few examples and the result always seems regular.

$\{\} \cap a^nb^n = \{\}$

$\lambda \cap a^nb^n = \lambda$

$ab \cap a^nb^n = ab$

(where $n \geq 0$ for $a^nb^n$)

When I try:

$a^nb^m \cap a^nb^n = a^nb^n$ which is not regular.

However, is $a^nb^m$ considered finite or infinite? $\{a^nb^m : m,n \geq 0\}$ is regular because there is a DFA for it. So, can it be considered finite?

$\endgroup$
2
  • 7
    $\begingroup$ The intersection of finite and infinite is certainly finite, hence regular $\endgroup$ Commented May 24, 2015 at 21:59
  • $\begingroup$ @HagenvonEitzen Can you tell me one thing ? What about inersection two finite regular languages ? If checking non-emptiness of this intersection is PSPACE-complete ? I know that this fact is hold for arbitrary regular languages. However, I would like to limit this fact to finite languages. $\endgroup$ Commented Jun 11, 2017 at 20:23

2 Answers 2

1
$\begingroup$

$\{a^nb^m:m,n\ge 0\}$ is a regular language, but it is clearly not finite. It contains one word for each ordered pair $\langle m,n\rangle\in\Bbb N\times\Bbb N$, so it has the same cardinality as the set $\Bbb N\times\Bbb N$ and is therefore countably infinite. Every finite language is regular, but there are many regular languages that are not finite. Indeed, for every non-empty finite set $F$ the language $F^*$ is regular and infinite.

The fact that every finite language is regular answers your first question, as Hagen pointed out in the comments: if $F$ is a finite language, and $L$ is any language, then $F\cap L$ is a finite language and therefore regular.

$\endgroup$
0
$\begingroup$

Well, I don´t knew if you knew it, but the intersection of an regular Language with an other one is regular. And every finite language is regular (proof: build an DFA).

If you now intertersect an finite with an infinite: Let´s look at the Intersection Property - In your finalSet will be only values, which were in BOTH Sets. -> So the size of the final Set is the Minimum of the two Sets. That means if you have an finite Language it is likely that your finalSet will also be an finite one.

$a^nb^m$ is an infinite Set (if you can build an DFA with an loop it´s mostly infinite [ just think about how you would make an DFA for $a^n \ldots$], but it´s regular for $n,m>=0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .