# How to prove that every regular language can be obtained by some FA?

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

• You mean "every regular language is accepted by some FA", don't you? – fade2black Sep 15 '17 at 16:59
• Yes! I don't understand how can we prove this definition – WOW Sep 15 '17 at 17:01
• 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. – David Richerby Sep 15 '17 at 17:27
• What now: is it a definition or theorem in your book? – Raphael Sep 15 '17 at 17:53
• How do you define regular languages? – 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.

• @rus9384 For better or worse, "finite automata" canonically refers to acceptors of regular languages, not other, extended (or restricted) models. – Raphael Sep 15 '17 at 19:08
• @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. – Raphael Sep 15 '17 at 19:45