HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Why is every finite language A ⊆ Σ* regular

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyfiniteregulareverylanguage

Problem

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can represent any finite language since the states would be finite as well?

Solution

The proof goes something like this:

  • If $A$ is a finite language, then it contains a finite number of strings $a_0, a_1, \cdots , a_n$.



  • The language $\{a_i\}$ consisting of a single literal string $a_i$ is regular.



  • The union of a finite number of regular languages is also regular.



  • Therefore, $A = \{a_0\} \cup \{a_1\} \cup \cdots \cup \{a_n\}$ is regular.

Context

StackExchange Computer Science Q#104322, answer score: 14

Revisions (0)

No revisions yet.