Automata

**Apprentice123** · July 4th 2010, 06:35 PM

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

Please, you have an example

**Swlabr** · July 5th 2010, 02:28 AM

Originally Posted by Apprentice123

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

Please, you have an example

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

**Apprentice123** · July 5th 2010, 08:33 AM

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

**Swlabr** · July 5th 2010, 08:47 AM

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?

**Apprentice123** · July 5th 2010, 04:24 PM

Originally Posted by Swlabr

Do you mean the case where there is only one state?

No. What happens when motion is empty (E)

**Apprentice123** · July 5th 2010, 05:36 PM

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

**Swlabr** · July 6th 2010, 12:58 AM

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?

**Defunkt** · July 6th 2010, 03:39 AM

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 \}$

**Apprentice123** · July 6th 2010, 06:14 AM

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

**Defunkt** · July 6th 2010, 06:40 AM

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/

**Apprentice123** · July 6th 2010, 07:20 AM

OK. But, how do you do?

Thread: Automata

LinkBack

Thread Tools

Display

Automata

Similar Math Help Forum Discussions

Automata Languages and DFA etc.

Finite Automata limitations

Stack automata

Help in Theory of Automata

Finite Automata question

Search Tags