Mon. Mar 10th, 2025

Automata theory and formal language

Algebraic Grammar

May 7, 2017

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

Post Views: 136

By My- Courses

Related Post

Automata theory and formal language

Regular ( or rational ) Expression

Dec 7, 2017 My- Courses

Automata theory and formal language

Sum and Product of Automata

May 21, 2017 My- Courses

Automata theory and formal language

Introduction to finite deterministic automata

May 9, 2017 My- Courses

Leave a Reply Cancel reply

You must be logged in to post a comment.

You missed

Exploring the Impact of Artificial Intelligence in Extended Detection and Response (XDR)

May 19, 2024

The annual cost for implementing security labels on smart devices would be less than $5 million

May 17, 2024

Careless Docker Users Expose Secrets, Warn German Researchers

May 16, 2024

Concerns Also Arise From Insiders

May 2, 2024