Results 1 to 3 of 3

Math Help - Describing an NFA in terms of a DFA

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Describing an NFA in terms of a DFA

    I have a theory question that seems to be the reverse of what's normally thought about. It seems the usual case is if when you have an NFA and you want to create a DFA using Rabin-Scott.

    So if we reverse this idea and we have a language, L, that is accepted by a DFA, M= (K,Alphabet,Transition Function, s, F) and the language accepted is any reversal of a string that exists in L, how would you precisely describe an NFA that accepts this language.

    Again, the answer is more theoretical than practical. I'm just finding it difficult to conceptualize and explain since I've only ever experienced going from an NFA to a DFA, not the other way around.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    Re: Describing an NFA in terms of a DFA

    Do you need an NFA for the language \{w^R\mid w\in L\} where L is accepted by a DFA M? This page has a two-line description of such NFA. If you don't need string reversals, then going from DFA to NFA is trivial since DFAs are NFAs.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    3

    Re: Describing an NFA in terms of a DFA

    I think the idea is to describe how the components of the quintuple, M=(K,Alphabet,Transition Function, s, F) could change if you had the latitude of using an NFA. I guess it is a strange question since as you said DFAs are NFAs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Describing Circles
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 9th 2011, 09:00 PM
  2. Describing a subspace
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 25th 2010, 05:09 AM
  3. Describing transformations
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 5th 2010, 03:11 PM
  4. Describing end behavior
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 25th 2009, 02:39 PM
  5. describing tranformations
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 9th 2008, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum