Search code examples
regular-languagedfa

How can I find the closure of a D FA


I am trying to implement the closure of D FA. I have successfully implemented Union, Compliment Intersection, Subtraction and Concatenation of D FA without using N FA. Our teacher did not tell us the algorithm to find the closure. I tried to do it by concatenating a D FA to itself but quite obviously it did not work.

I just need the steps by the way I am representing D FA by using matrix. Alongside can you please elaborate on Klein closure but I am sure I can can do that once I know how to get the closure.


Solution

  • I am not sure what you mean by closure in general. But for the Kleene closure you can proceed like this: from every final state you add an epsilon-transition (not reading anything) to the start state. So after reading one word of the language, you can start with another one.

    Of course, the resulting automaton is not deterministic any more. But there are standard procedures for determinizing it again.

    For a direct construction: look at all the transition that enter a final state, for example (q,a) -> f. From the outgoing state add another transition reading the same symbol and going to the start state: (q,a) -> s. So the automaton has the possibility to finish reading the word and just after that starting again.