Regular Language and Non-Regular Language

Question

Regular Language as I know of, is something that can be defined by a FSM. Non-Regular Language is something that consists of repetition which cannot be stored by the FSM.

I have found out that L( ababbababb ) is non-regular due to "ababb" is a repetition that cannot be stored by the FSM due to its limited memory. -> based https://www.youtube.com/watch?v=WrzaPNj9OZ4

However, all finite languages are regular, isnt L(ababbababb) supposed to be regular then?

Answer 1

Basic language definitions

Universal language over an alphabet $\Sigma$ is defined as a set of all strings of finite length (including the empty string of length zero, usually denoted as $\lambda$) over $\Sigma$. It is usually denoted as $\Sigma^{*}$.

Language over an alphabet $\Sigma$ is an arbitrary subset of $\Sigma^{*}$.

Basic language operations

Considering languages over one fixed alphabet $\Sigma$ (so all languages considered are a subset of $\Sigma^{*}$), we can define the following operations.

1. Set-theoretic operations: union, intersection, difference, etc.

2. Concatenation of languages $L_1$ and $L_2$ is defined as follows: $$L_1L_2 := \{l_1l_2 \ | \ l1 \in L_1,\ l_2 \in L_2\}$$ ($l_1l_2$ means appending string $l_2$ to the string $l_1$).

   • raising a language to non-negative integer power $k$ can now be defined:
     $L^{k} := $
     • $\{\lambda\}$, for $k = 0$
     • $L$, for $k = 1$
     • $L^{k-1}L$, for $k > 1$

3. Iteration of a language $L$ is denoted $L^{*}$ and defined as follows:
   $$L^{*} := \bigcup\limits_{k \ge 0}L^{k}$$

Regular languages

Regular language over an alphabet $\Sigma$ is defined recursively as follows:

1. $\ $ $\emptyset$ is a regular language
2. $\ $ $\{\lambda\}$ is a regular language
3. $\ $ $\forall a \in \Sigma$, $\{a\}$ is a regular language
4. $\ $ if $A$ and $B$ are regular languages:
   1. $A \cup B$ is a regular language
   2. $AB$ (concatenation) is a regular language
   3. $A^{*}$ (iteration) is a regular language
5. There are no regular languages, other than those described above.

It can be proven, that regular languages are precisely the languages which can be recognized by finite state automata, meaning that the above definition and the definition you've encountered are equivalent.

With the above definition it is easy to prove that finite languages are always regular. To see this notice that a finite language is a finite union of languages that contain only one word. Such languages are, in turn, a finite concatenation of languages that contain only one-letter words, that is $\{a\}, \ a \in \Sigma$, which is obviously regular, by above definition.

Backtracking on this and using the above definition, you see that a finite concatenation of these is regular, and that finite union of such languages is also regular.

Concrete example

Language $L := \{ababbababb\}$ can be considered over $\Sigma = \{a, b\}$. This means $\{a\}$ and $\{b\}$ are regular, hence $$L = \{a\}\{b\}\{a\}\{b\}\{b\}\{a\}\{b\}\{a\}\{b\}\{b\}$$ is regular too, as a finite concatenation of regular languages.