Social Icons

Monday, May 1, 2017

Introduction to formal language

1 - Introduction to formal language

The theory of formal languages {}{}was born within the domain of linguistics as a means of understanding the syntactic regularities of natural languages. In computer science, formal languages {}{}are used inter alia as a basis for defining programming languages.  Language theory is both a mathematical, computer and linguistic branch, a formal language is a set of symbol strings with a set of rules that are specific to it.  The alphabet of a formal language is the set of symbols or letters ... from which the chains of language can be formed; Often it is necessary to be finite. The strings formed from this alphabet are called words and the words that belong to a particular formal language are sometimes called well-formed words or well-formed formulas. A formal language is often defined by means of a formal grammar such as a regular grammar or a grammar out of context, also called its formation rule.  The domain of formal language theory mainly studies the purely syntactic aspects of these languages, that is, their internal structures.

2 - Alphabets, Words and Languages


\begin{example} $\Sigma =\{0,1,2,...\}=% %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion $ \ is an alphabet , $484,275,107,...$ \ are words \end{example}  \begin{notation} The set of words on $\Sigma $ \ will be noted  $\Sigma ^{\ast }$ \end{notation}  \begin{notation} The word that does not contain any letter is called, the empty word denoted \ $\wedge $ or $\varepsilon .$ \end{notation}  \begin{remark} We are interested only in the form of a word which may be arbitrary and we omit the meaning of the word example: avhbrtys, jorbqhegd, ... are words. \end{remark}
\subsection{Formal Language}  \begin{definition} A formal language is set of words  ( ie a subset of  $\Sigma ^{\ast }$ $)$ \end{definition}  \begin{example} $\{$ $CRMEF,Oujda,$ $Hay,$ $AlMassira$ $\}$ is language. \end{example}  \begin{example} $\{\Lambda ,a,aa,aaa,...\}=\{a^{n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$ is infinite language generated by a finite alphabet $\Sigma =\{a\}.$ \end{example}

3 - Operations on words and languages

\section{Operations on words and languages}  \subsection{Words concatenation}  \begin{definition} The concatenation of two words \ $x$ \ and \ $y$ \ is the word noed by \ $x.y $ \ or simply by\ $xy$\ defined by : \newline $x.y=xy$ \ ie \ if \ $x=x_{1}x_{2}...x_{r}$ \ and \ $y=y_{1}y_{2}...y_{s}$ \ then \ $x.y=x=x_{1}x_{2}...x_{r}$\ $y_{1}y_{2}...y_{s}$ \end{definition}  \begin{example} If $\ x=langu$ \ and \ $y=age$ \ then $x.y=language$ \end{example}
\subsection{Concatenation of  langauges}  \begin{definition} Let E and F be two languages of lthe alphabet $\Sigma .$ The concatenation \ of \ $E$ \ and \ $F$ \ is the language defined by : \newline $E.F=\{x.y/(x,y)\in E\times F\}$ \end{definition}  \begin{example} $E=\{u,v\}$ , \ $F=\{uv,vu\}$ \ $E.F=\{uuv,uvu,vuv,vvu\}$ \end{example}  $E.F$ \ Will be noted later by \ $EF$  \begin{definition} A language is said to be closed for the law "."\  If it is stable for concatenation ( i.e $\forall x,y\in E$ \ we have: $x.y\in E$ \end{definition}  \begin{example} $\{x^{n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$ \ is closed language\ $\ \ $but the language $\{x^{n}y^{m}/(n,m)\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \times  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion $ $\}$ is not closed. \end{example}

\begin{definition} Let\ $E$ \ be a language, the smallest closed language for the concatenation containing $E$ and $\{\wedge \}$ Is called the closure of $E$ \ and is noted by \ $E^{\ast }.$ $E^{\ast }$ is also called Kleene closure or Kleene star. \end{definition}  \begin{remark} $E^{\ast }=\underset{k\geq 0}{\cup E^{k}}$ \ ( where \ $E^{k}$ is the concatenation $E.E...E$ ) \end{remark}  \begin{example} Let \ $E$ \ be a language and\ $\ x$ \ a word of $E$ \ then we have:\newline $1)$ $\ \{x\}^{\ast }=\{x^{n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$\newline $2)$ \ $\{xx\}^{\ast }=\{x^{2n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$\newline $3)$ \ $\{xx,xxx\}^{\ast }=\{x^{n}/n\geq 2\}\cup \{\Lambda \}$\newline $4)$ \ $\{0,1\}^{\ast }$ \ Is the set of all natural integers containing only the numbers $0$ \ or \ $1.$\newline $5)$ \ $\varnothing ^{\ast }=\{\Lambda \}$ \end{example}

4 - Combinatorics on words

\section{Combinatorics of words}  \subsection{Length of words, prefixes and suffixes}  \begin{definition} The length of a word $x$ denoted $|x|$ , is the number of symbols that compose it. Example if $x=arbre$ alors $\ |x|=5$ \end{definition}  \begin{notation} Let $x$ be a word of $\Sigma ^{\ast }$ and $\sigma $ be a symbol of $\Sigma , $ the number of occurrences of $\sigma $ in $x$ is denoted \ by $\ |x|_{\sigma }.$ \end{notation}  \begin{example} $|arbre|_{r}=2,$ \ $|arbre|_{a}=1$ ,\ $|abbcb|_{b}=3$ \end{example}  \begin{definition} Let \ $x=x_{1}x_{2}...x_{r}$ be a word of $\Sigma ^{\ast }$ $\ $the words $% :\wedge ,$ $x_{1},$ $x_{1}x_{2},...,x_{1}x_{2}...x_{r}$ [ respectively $% \wedge ,$ $x_{r},$ $x_{r-1}x_{r},$ $x_{r-2}x_{r-1}x_{r}$\ ] Are called the prefixes of $x$ [ respectively the suffixes of $x]$ \end{definition}
\subsection{Parikh function's}  Let $\Sigma $ a finite and ordered alphabet, And can therefore be considered as a n-tuple $\Sigma =(\sigma _{1},\sigma _{2},...,\sigma _{n})$ the map $% \psi :\sum^{\ast }\rightarrow  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion ^{n}$ \ ,$x\longmapsto (|x|_{\sigma _{1}},|x|_{\sigma _{2}},...,|x|_{\sigma _{n}})$ is called \textbf{Parikh function's}  \begin{remark} For $n>1$ the parikh function's is not injective. \end{remark}  \begin{notation} for any word $x=x_{1}x_{2}...x_{r}$ \ we put \ $% \widetilde{x}=x_{r}x_{r-1}...x_{1}$ , and for any language $E$ \ we put : $% \widetilde{E}=\{\widetilde{x}/x\in E\}$ , $\widetilde{x}$ is\ called the mirror image of $x$, and \ $\widetilde{E}$ the mirror image of \ $E.$ \end{notation}  \begin{definition} We call palindrome, every word $x$, verifying\ : $\widetilde{x}=x$. \end{definition}  \begin{example} laval, \ radar \ are palindromes. \end{example}

5 - Regular Language

\section{Regular Language }  Let L be a language over alphabet $\Sigma $ We say that L is regular or rational if L can be obtained recursively by:  1) from the only basic languages:\newline $-$ language $\emptyset $\newline $-$ language $\{\wedge \}$ \ ( Language formed only by the \textbf{empty} symbol$)$\newline $-$ Language of the form $\{a\}$ where $a\in \Sigma $\newline $2)$By using only the following operations :\newline $-$ Unions operations\newline $-$ Concatenation\newline $-$ Kleene's star  \begin{example} The language $\{x^{n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}$ \ regular \end{example}  \begin{example} The language $L$ of the words of even length is rational since $L=(\Sigma ^{2})^{\ast }$ \end{example}  \begin{remark} Every finite language is regular \end{remark}  \begin{proposition} If $L$ is a regular language then $L^{\ast }$ is also. \end{proposition}  \begin{proposition} If\ $L_{1}$ $et\ L_{2}$ are regular then  $L_{1}\cdot L_{2}$ , $L_{1}\cup L_{2}$ \ and $L_{1}\cap L_{2}$ \ are regular. \end{proposition}

6 - Residual Language

\section{Residual Language}  \begin{definition} Let $L$ be a language over alphabet $\Sigma $ and $u$ a word of  $\Sigma ^{\ast }$, we get new language by putting $u^{-1}L=L/u=\{v\in \Sigma ^{\ast }/uv\in L\}.$ $L/u$ is called the residual language of the language $L$ with respect to word $u.$ \end{definition}  \begin{example} $L=\{uuv,uw,vv,uu\}$ alors $L/u=\{uv,w,u\}$ \end{example}  \begin{theorem} (Myhill Nerode theorem's) A language is recognizable if and only if it has only a finite number of residuals. \end{theorem}

7 - Topology on formal language

\section{Topology on formal language}  \subsection{Metric over language}  For any language $L$ on an alphabet $\Sigma $ we define a distance $% d:L\times L\longrightarrow  %TCIMACRO{\U{211d} }% %BeginExpansion \mathbb{R} %EndExpansion _{+}$ \ $(u,v)\longmapsto 2^{|u\wedge v|}$ where  $u\wedge v$ is the longest common prefix, moreover this distance is ultrametric $d(u,w)\leq \max (d(u,v),d(v,w))$  \subsection{Topology inductive limit on Kleene closure $X^{\ast }$}  We define a topology on  $X^{(k)}=X.X...X$ (The language on the alphabet $X$ formed of the words of length $k$) by conventioning that a part $O$ of $% X^{(k)}$ is open, if it is, any union  of the sets of the form : $% O_{1}.O_{2}...O_{k}$ ( Concatenation of $O_{i}$ ) where $O_{1},...,O_{k}$ are opens subsets of  $X.$ Then we equip the closing Kleene$X^{\ast }$ of the inductive limit topology associated at the family of canonical injections $i_{k}:X^{(k)}\hookrightarrow X^{\ast }$  \begin{remark} $X$ \ can be considered as a topological subspace of $X^{(k)}$ and consequently a topological subspace of $X^{\ast }\ $by means of continuous injections $i:X\hookrightarrow X^{(k)}$ $\ x\longmapsto x.\varpi ...\varpi $ \ where $\varpi $ is the empty word. \end{remark}  \begin{remark} Every language $L$ on the alphabet $X$ is considered as a topological subspace of $X^{\ast }$ for the induced topology. \end{remark}




Younes Derfoufi

No comments:

Post a Comment

Python Exercises With Solutions

  1. Exercises on Python Strings
  2. Exercises on Python lists
  3. OOP Exercices with solutions
  4. Exercises on Python File I/O
  5. Python Dictionary Exercises
  6. Python Sets Exercises
  1. Python Arithmetic Exercises
  2. Equations & System Of Equations
  3. Polynomials and Functions
  4. Python Arithmetic Exercises 
  5. Numpy, Matplolib, Sympy , Scipy - Exercises
  6. Python Arithmetic Exercises
  1. Python GUI Tkinter Exercises



Younes Derfoufi

Category Of Mobile Courses

Actualités (644) Adsense (1) Affiliation (1) Algebraic Topology (2) Algorithmic (1) all-news (30) Android (5) Android App (8) Android app without code (4) Android Apps (256) Android Development (4) Android download (2) Android OS (3) AngularJS (1) Automata theory and formal language (5) Bootstrap CSS (1) C programming (5) Category and Functor (8) CMS (3) Computer Glossary (18) Create Mobile App With Ionic Framework (2) CSS (2) CSS-Cascading-Style-Sheets (4) Developpement Java (13) Differential Geometry (1) Django-Python-Framework (9) dropshiping (26) Earn Money by Internet (4) Emplois (23) Framework php (2) Fraud (2) HTML (7) Java For Beginners (10) Javascript (12) Kotlin Programming Language (8) Kotlin For Mobile Android (1) Linux Download (2) Marketing (5) Mobile (3) Mobile Courses (4) Mobile Marketing (4) MoneyGram (1) News (721) Node.js (5) Open Source (1) Photoshop (1) Protect Computer (1) Python (35) Python BeautifulSoup (1) Python For Data Science (2) Python PyQt (4) Python Reference (1) Python-Books (6) Python-DVD-Training (1) Python-Exercises (263) Python-Framework (1) Python-IDE (1) Python-Kivy-Framework (2) Python-Modules (1) Python-pdf (2) Python-pyQt (1) Référencement (2) Script PHP (2) Security (6) SEO (1) Snipping Tool: Faq (1) Social Networks (1) Source Code (1) Statistics With SPSS (2) Surveillance Software (1) Travail à domicile (6) Tutoriels php en vidéos (2) Tutoriels-MySql (6) tutoriels-php (19) Utilitaires (1) VPS (1) Web Hosting (1) Webcam (1) Webmarketing (11) Western Union (1) Windows 10 (1) Windows 7 (4) Windows 7 Faq (2) Windows 8 (1) Windows Accessories (1) Windows Download (8) Windows Drivers (1) Windows Fonts (1) Windows Power Shell (2) Windows Registry (2) Windows Security (18) Windows Software (2) Windows Spyware (2) Windows utilities (3) Windows Virus (2) Windows Vista (3) Windows Wireless (1) Windows xp (1) Wordpress (1)
 

Sample text

Sample Text

 
Blogger Templates