0
$\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?

$\endgroup$
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.

$\endgroup$
  • $\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 '18 at 15:01
  • 2
    $\begingroup$ You can use two DFAs. It's just going to be much harder. $\endgroup$ – David Richerby Sep 5 '18 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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