Regular language

a Language is considered regular if there exists a DFA $M$ such that $L(M)=A$. that is, the problem encoded by language $A$ can be solved by a definite state automata.

Example

a regular language could be $A=\{w\mid w\text{ ends with the symbol “a"}\}$. here, we could probably construct an automata $M$ that only uses two states.

Example

a non-regular language could be $A=\{count(w\text{, a})=count(w\text{, b})\}$. the number of states to consider is not finite, and therefore a DFA cannot be constructed for it.

proving a language is not regular

Theorem

if there exists an infinite set $S$ of pairwise, distinguishable strings w.r.t. a language $A$, then $A$ cannot be regular.

this follows from the idea that a set $|S|=k$ of pairwise distinguishable strings corresponds to a DFA having at least $k$ states. if $S$ is infinite, then a finite-state automata cannot exist! (infinite states)

converse also holds: if $A$ is not regular, then an infinite number of pairwise distinguishable strings exist w.r.t. to language $A$.