1
$\begingroup$

If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how would I solve this?

I was considering an approach where I alternate between accepted even multiples of the DFA and unaccepted odd multiples, and essentially connect two copies of the original DFA together to create the even-DFA. However, if I have multiple accept states within the original language this would complicate things as I would need to allow connections from all of these states, and would then need to consider the presence of self-loops.

This will be implemented in Haskell, but insight either from the logic point of view or the coding point of view would be greatly appreciated.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean: another DFA which accepts all the strings...? $\endgroup$
    – ShyPerson
    Commented Oct 16, 2023 at 3:07
  • $\begingroup$ Append a diagram of a toy DFA and I will post the Haskell code. $\endgroup$
    – Rodrigo de Azevedo
    Commented Nov 30, 2023 at 8:50
  • $\begingroup$ On Haskell, you might want to take a look at this $\endgroup$
    – Rodrigo de Azevedo
    Commented Nov 30, 2023 at 9:54

1 Answer 1

Reset to default
1
$\begingroup$

The language you are considering is $(W^2)^*$, so you could combine standard constructions for the concatenation and the star operation.

Improve this answer
$\endgroup$

Your Answer

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

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