# Math Help - Automata

1. ## Automata

How to transform a non-deterministic finite automaton (with or without empty moves) in a deterministic finite automaton?

2. Originally Posted by Apprentice123
How to transform a non-deterministic finite automaton (with or without empty moves) in a deterministic finite automaton?

Wikipedia seems to cover this well, with quite a neat example!

3. OK. I know how to turn a non-deterministic finite automaton into a deterministic finite automaton. But if the non-deterministic have empty movements I do not know how to turn

4. Originally Posted by Apprentice123
OK. I know how to turn a non-deterministic finite automaton into a deterministic finite automaton. But if the non-deterministic have empty movements I do not know how to turn
Do you mean the case where there is only one state?

5. Originally Posted by Swlabr
Do you mean the case where there is only one state?
No. What happens when motion is empty (E)

6. To convert NFA (empty movements) in DFA. Is there an algorithm? I have to remove the empty movements before converting? How to remove?

7. Originally Posted by Apprentice123
To convert NFA (empty movements) in DFA. Is there an algorithm? I have to remove the empty movements before converting? How to remove?
Sorry, I am not entirely sure what you mean by movements then. An automata consists of a 5-tuple, $(Q, \Sigma, T, \iota, F)$ where $Q$ is the set of states, $\Sigma$ is your alphabet, $T: Q \times \Sigma \rightarrow \mathcal{P}(Q)$ is your transition function (lines), $\iota \in Q$ is your start state and $F \subseteq Q$ is the set of terminating sets.

Which of these are you wanting to be empty, if any?

8. This should be in your lecture notes:

Let $EM = (Q, \Sigma, q_0, \delta _{EM}, F_{EM})$ be a non-deterministic automaton with epsilon-travels ("empty movements")

Then the equivalent non-deterministic automaton without epsilon travels is $ND = (Q, \Sigma, q_0, \delta _{ND}, F_{ND})$ where:

$\forall q \in Q, \sigma \in \Sigma, \ \delta_{ND}(q, \sigma) = \delta_{EM}(q, \sigma)$ (this means that any state that was reachable from $q$ with epsilon-travels and input $\sigma$, is now reachable from $q$ only with input $\sigma$)

and

if $\epsilon \notin L(EM)$ then $F_{ND} = F_{EM}$
if $\epsilon \in L(EM)$, then $F_{ND} = F_{EM} \cup \{q_0 \}$

9. Do you have any examples? Could you explain the steps in the conversion?

10. Sure:

Take a look at the images I attached. The one with EM is the original automaton, and the one with ND is what it should look like after the 'conversion'.

http://img821.imageshack.us/i/28510076.jpg/

http://img202.imageshack.us/i/51132577.jpg/

11. OK. But, how do you do?