I have seen this definition almost everywhere, but I don't know the underlying proof behind this definition.

  • $\begingroup$ You mean "every regular language is accepted by some FA", don't you? $\endgroup$ – fade2black Sep 15 '17 at 16:59
  • $\begingroup$ Yes! I don't understand how can we prove this definition $\endgroup$ – WOW Sep 15 '17 at 17:01
  • 3
    $\begingroup$ This is covered by any textbook on automata theory. Furthermore, many people take acceptance by DFAs to be the definition of regular languages. You don't prove definitions. $\endgroup$ – David Richerby Sep 15 '17 at 17:27
  • $\begingroup$ What now: is it a definition or theorem in your book? $\endgroup$ – Raphael Sep 15 '17 at 17:53
  • $\begingroup$ How do you define regular languages? $\endgroup$ – Yuval Filmus Sep 16 '17 at 6:13

These definitions are from Wikipedia

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using a regular expression...


Alternatively, a regular language can be defined as a language recognized by a finite automaton.

You can define a regular language as a set of strings accepted by some FA. In this case you don't have to prove anything since a regular language is recognized by a finite automaton by definition.

But if you define a regular language as a formal language that can be expressed using a regular expression then you can prove that it is accepted by some FA using Thompson construction, i.e. prove the equivalence of regular expressions and finite automata.

  • $\begingroup$ @rus9384 For better or worse, "finite automata" canonically refers to acceptors of regular languages, not other, extended (or restricted) models. $\endgroup$ – Raphael Sep 15 '17 at 19:08
  • 1
    $\begingroup$ @rus9384 I have no idea what that is. All I'm saying is that you shouldn't say "some FA can decide non-regular languages" without explanation, since novices will take it to mean "some NFA can ..." which is wrong. $\endgroup$ – Raphael Sep 15 '17 at 19:45

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.