Social Icons

Sunday, May 7, 2017

Algebraic Grammar

1 - Concept of Grammar

\chapter{Free context  grammar}  \section{Concept of Grammar}  \begin{definition} We call algebraic grammar or free context \ grammar aany 4-tuple $% G=(V,\Sigma ,P,S)$ where :\newline $-$ $\Sigma $ Is a finite set called an alphabet whose elements are called terminal symbols\newline $-$ $V$ Is another alphabet whose elements are called \ a variables or non-terminal symbols such that $V\cap \ \Sigma =\emptyset $\ \newline $-$ $S$ is an element of $V$ called the initial symbol.\newline $-$ $P$ is finite subset of $V\times (\Sigma \cup V)^{\ast }$ called the set of derivation's rules or production's rules of $G.$ \end{definition}  \begin{notation} The elements of $V$ are denoted by the uppercase letters $A,B,C...$While the elements of $\ \Sigma $ are denoted by the lowercase letteres $a,b,c....$ \end{notation}  \begin{notation} A rule $(A,w)\in P$ is denoted by $A\rightarrow w.$ A set of rules formed from a single variable $A$ : $A\rightarrow w_{1},A\rightarrow w_{2},...,A\rightarrow w_{n}$ will be noted simply $A\rightarrow w_{1}|w_{2}|...|w_{n}.$ \end{notation}

2 - Language generated by grammar



\section{Language generated by a grammar}  Let  $G=(V,\Sigma ,P,S)$ be algebraic grammar  \begin{remark} Starting from the initial symbol and executing a finite number of rules of $P $ we obtain a language denoted by $L(G)$ called the language generated by the grammar $G.$ \end{remark}  \begin{example} $G=(V,\Sigma ,P,S)$ $V=\{S\}$ $,$ $\Sigma =\{a,b\}$ and $P=\{(S,aSb),(S,% \varepsilon )\}$ ( $P$ can be schematized by $S\rightarrow aSb$ \ and \ $% S\rightarrow \varepsilon )$ \end{example}  To verify, for example, that the word $ab\in L(G)$, we will successively execute the two rules $\underline{S}\rightarrow a\underline{S}b\rightarrow a% \underline{\varepsilon }b=ab.$ In each step we have underlined a letter to indicate the letter that will be replaced in the next step). In the same way we verify that the word $a^{2}b^{2}\in L(G):$ by executing successuvely the rules $\underline{S}\rightarrow a\underline{S}b\rightarrow aa\underline{S}% bb\rightarrow aa\underline{\varepsilon }bb=a^{2}b^{2}$. And so on, by recurrence we obtains $L(G)=\{a^{n}b^{n}/n\in  %TCIMACRO{\U{2115} }% %BeginExpansion \mathbb{N} %EndExpansion \}.$  \begin{definition} A free context \ grammar is called right regular, if all these rules are of one of the following types: $A\rightarrow a$ \ , $A\rightarrow aB$ \ , $% A\rightarrow \varepsilon $ where $A,B$ are variables of $V$ \ and $a\in \Sigma .$ It is called left regular if all its rules are of one of the following types : $A\rightarrow a$ \ , $A\rightarrow Ba$ \ , $A\rightarrow \varepsilon .$ \end{definition}  \begin{example} $G=(V,\Sigma ,P,S)$ $V=\{S\}$ $,$ $\Sigma =\{a,b\}$ and $\ P$ : $% S\rightarrow aS$ $|$ $\varepsilon $ \ $G$ \ is grammar left regular. \end{example}  \begin{theorem} A language  $L$ is rational (regular )  If and only if there exists a regular grammar $G$ (right or left) such that $L=L(G).$ \end{theorem}

Younes Derfoufi

No comments:

Post a Comment

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) 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-Books (6) Python-DVD-Training (1) Python-Exercises (213) 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