Results 1 to 2 of 2

Math Help - Proving NFA Correctness

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    92

    Proving NFA Correctness

    Question:

    Formally prove the correctness of the union construction as follows. Let M1 and M2 be the two \lambda-NFA's constructed for R1 and R2 and let N be the \lambda-NFA constructed so that L(N) = R1 + R2. Let w be a string such that \Delta_{N}^{*}(\iota,w,f). Prove that either \Delta_{M_{1}}^{*}(\iota_{1},w,f_{1}) or \Delta_{M_{2}}^{*}(\iota_{2},w,f_{2}). Use induction on all strings w.

    Not only do I have no idea what to do, I don't even know what this is asking. Any push in the right direction would be helpful.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,501
    Thanks
    765
    Here is my guess about the concepts and notations. Feel free to correct.

    The empty word is denoted by \lambda. A \lambda-NFA is a nondeterministic automaton that can change state without reading any symbols. R1 and R2 are regular expressions, and + denotes the union ("or") of regular expressions. \Delta_N^*(\iota,w,f) probably means that the automaton N reads the word w and moves from state \iota to state f.

    You must have been given a way to construct an NFA N that accepts (L1 union L2) from two NFA's M1 and M2 that accept L1 and L2, respectively. N just has a new initial state that nondeterministically and without reading any symbols changes into either the initial state of M1 or the initial state of M2. After that it behaves like M1 or M2. You have to show that if w is accepted by N, then it is accepted by M1 or by M2 (and, presumably, the other way around).

    This is kind of obvious because the only thing N can do is to become either M1 or M2, so to speak. However, to be very formal, one may need to invoke induction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Check derivtives for correctness
    Posted in the Calculus Forum
    Replies: 5
    Last Post: January 16th 2011, 12:09 PM
  2. Correctness
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 27th 2009, 09:15 AM
  3. Program Correctness Proof
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 24th 2009, 10:12 PM
  4. Proving correctness of a loop using Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 25th 2008, 08:38 PM
  5. Correctness of a sample function
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 25th 2006, 11:32 AM

Search Tags


/mathhelpforum @mathhelpforum