Describing an NFA in terms of a DFA

• Sep 16th 2011, 10:25 AM
davidp007
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.
• Sep 16th 2011, 03:05 PM
emakarov
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.
• Sep 16th 2011, 05:09 PM
davidp007
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.