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 symbolsnewline $-$ $V$ Is another alphabet whose elements are called  a variables or non-terminal symbols such that $Vcap  Sigma =emptyset $ newline $-$ $S$ is an element of $V$ called the initial symbol.newline $-$ $P$ is finite subset of $Vtimes (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 $Arightarrow w.$ A set of rules formed from a single variable $A$ : $Arightarrow w_{1},Arightarrow w_{2},...,Arightarrow w_{n}$ will be noted simply $Arightarrow 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 $Srightarrow aSb$  and  $% Srightarrow varepsilon )$ end{example}  To verify, for example, that the word $abin L(G)$, we will successively execute the two rules $underline{S}rightarrow aunderline{S}brightarrow 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 aunderline{S}brightarrow aaunderline{S}% bbrightarrow aaunderline{varepsilon }bb=a^{2}b^{2}$. And so on, by recurrence we obtains $L(G)={a^{n}b^{n}/nin  %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: $Arightarrow a$  , $Arightarrow aB$  , $% Arightarrow varepsilon $ where $A,B$ are variables of $V$  and $ain Sigma .$ It is called left regular if all its rules are of one of the following types : $Arightarrow a$  , $Arightarrow Ba$  , $Arightarrow varepsilon .$ end{definition}  begin{example} $G=(V,Sigma ,P,S)$ $V={S}$ $,$ $Sigma ={a,b}$ and $ P$ : $% Srightarrow 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

Leave a Reply