[Solved]: What is the difference between formal language, regular language and regular expression?

Problem Detail: 

I want to know the difference between these three languages and it would be great if you would give some examples as well, thank you. :)

Asked By : hackhan

Answered By : Yuval Filmus

An alphabet $\Sigma$ is a finite collection of symbols. For example, $\Sigma = \{0,1\}$.

A word over an alphabet $\Sigma$ is a finite sequence of letters from $\Sigma$. For example, $0$, $01$ and $1110$ are all words over $\{0,1\}$. The empty word (that is, the empty sequence) is also allowed, and denoted $\epsilon$ (or sometimes $\lambda$).

The collection of all words over $\Sigma$ is denoted $\Sigma^*$.

A formal language over an alphabet $\Sigma$ is a set of words over $\Sigma$. Equivalently, a formal language over $\Sigma$ is a subset of $\Sigma^*$.

A regular language over $\Sigma$ is a formal language over $\Sigma$ which is accepted by some DFA.

A regular expression over $\Sigma$ has the following syntax:

1. $\epsilon$ is a regular expression.
2. $\sigma$ is a regular expression for all $\sigma \in \Sigma$.
3. If $r_1,r_2$ are regular expressions then so are $(r_1)^*$, $(r_1+r_2)$ and $(r_1r_2)$.

In practice we don't write all the parentheses. Each regular expression denotes some formal language (you will learn this translation in class). It turns out that a formal language is regular if and only if there is some regular expression denoting it.

If you have any more questions, I recommend reading a textbook which covers regular languages, for example Hopcroft and Ullman.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55013

 Ask a Question

 Download Related Notes/Documents