[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