Results 1 to 11 of 11

Math Help - Automata

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Automata

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


    Please, you have an example
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Apprentice123 View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Apprentice123 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Quote Originally Posted by Swlabr View Post
    Do you mean the case where there is only one state?
    No. What happens when motion is empty (E)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2008
    Posts
    829
    To convert NFA (empty movements) in DFA. Is there an algorithm? I have to remove the empty movements before converting? How to remove?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Apprentice123 View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    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 \}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Do you have any examples? Could you explain the steps in the conversion?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    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/
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. But, how do you do?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Automata Languages and DFA etc.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 20th 2011, 09:32 AM
  2. Finite Automata limitations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 6th 2010, 10:57 AM
  3. Stack automata
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: August 27th 2010, 05:28 AM
  4. Help in Theory of Automata
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 06:04 AM
  5. Finite Automata question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: July 7th 2009, 03:33 PM

Search Tags


/mathhelpforum @mathhelpforum