Regular expression and DFA/NFA questions

Question

If a language L is generated by a regular expression, then L is recognized by a DFA.

I think this is true, because regular expressions describe regular languages, those of which are exactly accepted by DFAs.

If a language L is recognized by an NFA, then L is generated by a regular expression.

I think this is true as well, because all NFAs are DFAs, and the class of languages accepted by DFAs are regular languages which can be expressed as regular expressions.

Am I confusing any topics here? I'd appreciate any clarifications or intuitive explanations if my understanding seems wrong.

Answer 1

No, you're right. The following conditions on a language $L$ are equivalent:

1. There is a DFA that accepts $L$.
2. There is an NFA that accepts $L$.
3. There is a regular expression that describes $L$.
4. There is a regular grammar that generates $L$.

-- that is, a language that satisfies any one of these conditions will also satisfy the others. In other words, each of these conditions describe the same class of languages, which is known as the "regular languages".

---

If the question is homework, it may be that you're asked to prove one of these equivalences, not just state that you know it's the case. How you would go about proving it depends on what you already have proof of, but typically you would describe a concrete algorithm that takes a regular expression (or a NFA) as input and produces a DFA (or a regular expression) for the same language as output, together with an argument that the output does indeed describe the same language as the input.

Answer 2

A DFA is an NFA, but an NFA is not in general a DFA, contrary to your claim. What is true however, is that any NFA is equivalent to some DFA (equivalent means that they recognize the same language), but this needs a proof, known as the subset construction.