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


closed as unclear what you're asking by David Richerby, Tom van der Zanden, Luke Mathieson, hengxin, vonbrand Mar 30 '16 at 15:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ What research did you do before asking here? This is all covered by any textbook or set of lecture notes, and there are many of them. For example, a regular language is some kind of set of strings, whereas a regular expression is a description of a set of strings. There's little point in writing out this stuff again when it's already available in so many places. Do you have a more specific question? $\endgroup$ – David Richerby Mar 27 '16 at 17:05
  • $\begingroup$ i searched wikipedia for the definitions and for formal language there was written that it "In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols that may be constrained by rules that are specific to it." and i think a regular language is also created by following some rules (regular expression) so i wanted to know what is the difference between theses two $\endgroup$ – hackhan Apr 2 '16 at 9:36

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.

  • $\begingroup$ A regular language over ΣΣ is a formal language over ΣΣ which is accepted by some DFA. - or can be described using regural expression and regural grammar, correct? $\endgroup$ – Max Koretskyi aka Wizard Oct 18 '17 at 7:38
  • 1
    $\begingroup$ Yes, there are many equivalent definitions. $\endgroup$ – Yuval Filmus Oct 18 '17 at 7:39
  • $\begingroup$ thanks, just wanted to make sure I understand this answer correctly $\endgroup$ – Max Koretskyi aka Wizard Oct 18 '17 at 7:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.