1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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'$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.