Question

I have course notes which claim the following two facts:

First, DFAs recognize exactly the regular languages.

Second, regular languages are closed under union, concatenation, and *.

Now I have as an exercise constructed a DFA which recognizes strings from {0,1} which have an odd number of 1s. So the language of strings of any odd number of 1s is a regular language. However, if you concatenate any two words from the language it contains an even number of 1s and is therefore not closed under concatenation.

I must be misunderstanding something, but what?

I think maybe what I'm doing is saying that the language itself is closed under concatenation, when that's not true. Maybe the claim is actually that the concatenation of one regular language with another regular language is a third regular language?

Was it helpful?

Solution

The third paragraph is the correct description how to interpret the statement from your notes. This is also easy to prove: Say $L$ and $L'$ are regular languages described by some regular expressions $r$ and $r'$ respectively. Then $rr'$ describes the concatenation $LL'$ of $L$ and $L'$.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top