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:
- $epsilon$ is a regular expression.
- $sigma$ is a regular expression for all $sigma in Sigma$.
- 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