1
$\begingroup$

Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.

Is there an alternative proof that goes on to show that regular languages are also closed under concatenation using DFAs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Using NFAs does prove the result for regular languages, since NFAs accept exactly the regular languages. In principle, one could give a proof using DFAs but it's likely to be very fiddly and probably not enlightening. It's much easier to give the proof using NFAs and separately show that anything accepted by an NFA is also accepted by a DFA.

Indeed, it's even easier to give the proof using regular expressions! This is part of the point behind giving the three equivalent characterizations of the regular languages: it means that, when you want to prove something about regular languages, you can use whatever system makes the proof easiest.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you, but is there a way to prove that I can't use DFAs to show concatenations of regular languages? I know that DFAs are more inefficient compared to NFAs, but there should be a way for the equivalence to work right? $\endgroup$
    – Francis
    Sep 5, 2018 at 15:01
  • 2
    $\begingroup$ You can use two DFAs. It's just going to be much harder. $\endgroup$
    – David Richerby
    Sep 5, 2018 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.