0
$\begingroup$

Given $L$ a non-regular language and $F$ a finite language I need to prove, or disprove, that $L^+ \cap F$ is a regular language. I tried to prove this using induction on the number of words in $L^+ \cap F$, as from $F$ finite nature I get that the intersection is also finite, hence:

  1. $n = 0$, There no words in $L^+ \cap F$ and the empty set is a regular language so the statement stands
  2. Let's assume that for $n\in\mathbb{N}$, the number of words in $L^+ \cap F$, the intersection is a regular language
  3. for $k = n + 1, k\in\mathbb{N}$ I know from the assumption of the induction that there is an automaton for the first $n$ words in the intersection so we can add a new chain of states (or a path) to that automaton with the final state the one accepting the kth word, therefore $L^+ \cap F$ is a regular language

In my head, this seems to be a sufficient proof, but I still feels as if the last part for $n + 1$ is lacking something.

I then tried a different approach, I know $F$ is finite and therefore regular and has an automaton, and as $L^+ \cap F$ is a subset of $F$ I can take the automaton for $F$ and remove the paths for the words in $F - L^+ \cap F$ leaving an automaton for every word in $L^+ \cap F$, hence the intersection is a regular language. But while the second explanation seems better, to me at least, it doesn't feel like a formal proof

$\endgroup$
3
  • $\begingroup$ Hint: A subset of a finite set is finite. $\endgroup$ Mar 20, 2022 at 21:58
  • $\begingroup$ ... And every finite language is regular $\endgroup$
    – rici
    Mar 20, 2022 at 22:12
  • 1
    $\begingroup$ oh I see it now, I just went full retard $\endgroup$ Mar 20, 2022 at 22:39

0

Your Answer

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

Browse other questions tagged or ask your own question.