Results 1 to 2 of 2
  1. #1

    Translate an algorithm to C program

    my problem is that i have written an algorihtm to convert non deterministic finite automata to deterministic finite automata but i couldn't translate it to C program and this is the algorithm i have written
    qx is a state in the NFA and q0 is its start state
    QX is a state in the DFA and Q0 is its start state
    The eqsilon-closure of a DFA state consists of all the states in the NFA that we can get to with epsilon moves from the states in the DFA state.
    Q0 = { q0 }
    // but there are some states we can reach from q0 at no cost
    Q0 = epsilon-closure(Q0)
    while there are states we haven't processed
    pick one such state, Qn
    for each symbol s
    let tmp be a new, empty, set
    for each q in Qn
    add delta(q,s) to tmp
    end for
    tmp = epsilon-closure(tmp)
    if tmp is not in the DFA then
    let Qi be a new state
    Qi = tmp
    add Qi to the DFA
    else
    let Qi be the state equivalent to tmp
    end if
    add an edge from Qn to Qi in the automaton
    end for
    end while
    for each Qi
    if there is a q in Qi that is a final state then
    Qi is a final state
    end if
    end for
    i was wondering if you would mind helping me to translate it to a C program that convert NFA to DFA.

    i'm looking forward to getting your answer

  2. #2
    Sounds like a homework assignment for a class....?

    I'm sure if you poked around the net you'll find a prewritten NFA->DFA converter.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •