I want to know the difference between these three languages and it would be great if you would give some examples as well.
-
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 RicherbyMar 27, 2016 at 17:05
-
1$\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$– hackhanApr 2, 2016 at 9:36
1 Answer
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.
-
$\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$ Oct 18, 2017 at 7:38
-
1$\begingroup$ Yes, there are many equivalent definitions. $\endgroup$ Oct 18, 2017 at 7:39
-
$\begingroup$ thanks, just wanted to make sure I understand this answer correctly $\endgroup$ Oct 18, 2017 at 7:40