Lab Session #11 #

Agenda #

Generative Grammars Chomsky Hierarchy Context-Free Grammars: Backus-Naur Form

Models #

Automata (operational models): #

Models suitable to recognize/accept, translate, compute language: receive an input string and process it.

Grammar (generative models): #

Models suitable to describe how to generate a language: set of rules to build phrases of a language.

Grammars #

A grammar is a set of rules to produce strings. #

A grammar is a tuple: $\langle V_N, V_T, P, S \rangle$ , where:

$V_N$ is the non-terminal alphabet
$V_T$ is the terminal alphabet;
$P$ is the terminal alphabet;
$S$ is the terminal alphabet;
$V = V_N \cup V_T$ the alphabet;
$P \subseteq \left(V^* \cdot V_N \cdot V^*\right) \times V^*$ is the (finite) set of rewriting rules of production;
$S \in V_N$ is a particular element called axiom or initial symbol.
A grammar $\langle V_N, V_T, P, S\rangle$ generates a language on V_T.

Terminal symbols are elementary symbols - cannot be broken down into smaller units i.e. cannot be changed using the production rules of the grammar.

Non-terminal symbols - can be replaced by groups of terminal and non-terminal symbols according to the production rules.

Production Rule #

Let $G = \langle V_N, V_T, P, S\rangle$ be a grammar.

A production rule $\alpha \rightarrow \beta$ is an element of $P$ , where:

$\alpha \in V^* \cdot V_N \cdot V^*$ is a sequence of symbols including at least one non-terminal symbol.
$\beta \in V^*$ is a (potentially empty) sequence of (terminal or non-terminal) symbols.

Chomsky Hierarchy #

Chomsky hierarchy	Grammars	Languages	Miniamal automaton
type 0	Unrestricted	Recursively enumerable	Turing machine
type 1	Context-sensitive	Context-sensitive	LBA
type 2	Context-free	Context-free	NDPDA
type 3	Regular	Regular	FSA

Strictly Regular grammars (type 3) #

Production rules are restricted to a single non-terminal on the left-hand side and a right-hand side consisting of a single terminal, possibly

followed by a single non-terminal - right grammar
preceded by a single non-terminal - left grammar

Example: #
Generate language with the strings of alternating a’s and b’s:
$V_N = \{S, A, B\}; \hspace{0.2cm}$
$V_T = \Sigma_1 = \{a, b\}$
Set of Production rules P: #
$S \rightarrow A$
$S \rightarrow B$
$A \rightarrow aB$
$A \rightarrow \epsilon$
$B \rightarrow bA$
$B \rightarrow \epsilon$

Strictly Regular grammars #

Strictly Right regular grammar

Strictly Right regular grammar #

A right regular grammar is a formal grammar, such that all the production rules in P are of one of the following forms:

$A \rightarrow b$

where

A \in V_N

and

b \in V_T

$A \rightarrow bB$

where

A, B \in V_N

and

b \in V_T

$A \rightarrow \epsilon$

where A

\in V_N

and

\epsilon

denotes the empty string.

Strictly Left regular grammar

Strictly Left regular grammar #

A left regular grammar is a formal grammar, such that all the production rules in P are of one of the following forms:

$A \rightarrow b$

where

A \in V_N

and

b \in V_T

$A \rightarrow Bb$

where

A, B \in V_N

and

b \in V_T

$A \rightarrow \epsilon$

where

A \in V_N

and

\epsilon

denotes the empty string.

Extended regular grammars #

Extended Right regular grammar

Extended Right regular grammar #

A right regular grammar is a formal grammar, such that all the production rules in P are of one of the following forms:

$A \rightarrow b$

where

A \in V_N

and

b \in V_T

$A \rightarrow wB$

where

A, B \in V_N

and

w \in V_T^*

$A \rightarrow \epsilon$

where

A \in V_N

and

\epsilon

denotes the empty string.

Extended Left regular grammar

Extended Left regular grammar #

A left regular grammar is a formal grammar, such that all the production rules in P are of one of the following forms:

$A \rightarrow b$

where

A \in V_N

and

b \in V_T

$A \rightarrow Bw$

where

A, B \in V_N

and

w \in V_T^*

$A \rightarrow \epsilon$

where

A \in V_N

and

\epsilon

denotes the empty string.

Exercises #

Define Strictly Regular grammars that produce the following languages over the alphabet:

$\Sigma_1 = \{a, b\} , \Sigma_2 = \{0, 1\}$
$L_1 = \{0,1\}^*$
$L_2 = \{(aab \hspace{0.2cm} | \hspace{0.2cm} bba)^*\}$

Solutions #

Solutions

Solutions L1

L_1 = \{0,1\}^*

V_N = {S} \hspace{0.2cm}

V_T = \Sigma_2 = \{0,1\}

Set of Production rules P:

$S \rightarrow \epsilon$

$S \rightarrow 0S$

$S \rightarrow 1S$

Solutions L2

L_2 = \{(aab \hspace{0.2cm} |\hspace{0.2cm} bba)^*\}

V_N = \{S, A, B, F, E\} \hspace{0.2cm}

V_T = \Sigma_1 = \{a, b\}

Set of Production rules P:

$S \rightarrow \epsilon$

$S \rightarrow aA$

$S \rightarrow bB$

$A \rightarrow aF$

$F \rightarrow bS$

$B \rightarrow bE$

$E \rightarrow aS$

Homework: #

$L_3 = \{(aa \hspace{0.2cm} | \hspace{0.2cm} bb)^*aa \}$
$L_4 = \{(00^* 11^*)\}$

Context-Free grammars (type 2) #

Defined by rules of the form $A \rightarrow \gamma$ where $A$ is a non-terminal and $\gamma$ is a string of terminals and non-terminals.

Example #
Generate language:
$a^nb^n,$
where $n>0$
$V_N = \{S\}; \hspace{0.2cm}$
$V_T = \Sigma_1 = \{a, b\}$
Set of Production rules P: #
$\{ S \rightarrow aSb | ab\}$

Exercises #
Define context-free grammars that produce the following languages over the alphabet:
$\Sigma = \{a, b\}$
$L_1 = \{w ∈ \{a, b\}^∗| w = w^R\}$
$L_2= \{a^ib^jc^k | i, j, k \geq 0 and i=j or i=k \}$
Homework:
$L_3 = Generate language with alternating a's and b's$
$L_4 = \{a^nb^nc^m \mid n,m>0\} \cup \{a^nb^mc^m \mid n,m>0\}$

Solutions #

Solutions

Solution L1

L_1 = \{w ∈ \{a, b\}^∗ | w = w^R\}

V_N = \{S, O, E\} \hspace{0.2cm}

V_T = \Sigma = \{a, b\}

Set of Production rules P:

$S \rightarrow O \hspace{0.2cm} | \hspace{0.2cm} E$

$E \rightarrow \epsilon \hspace{0.2cm} |\hspace{0.2cm} aEa \hspace{0.2cm} \hspace{0.2cm} | \hspace{0.2cm} bEb$

$O \rightarrow a \hspace{0.2cm}|\hspace{0.2cm} b \hspace{0.2cm} | \hspace{0.2cm} aOa\hspace{0.2cm} |\hspace{0.2cm} bOb$

or:

$S \rightarrow aSa \hspace{0.2cm} |\hspace{0.2cm} bSb \hspace{0.2cm}|\hspace{0.2cm} a \hspace{0.2cm}|\hspace{0.2cm} b\hspace{0.2cm} |\hspace{0.2cm} e$

Solution L2

L_2= \{a^ib^jc^k | i, j, k \geq 0 and i=j or i=k\}

V_N = \{S, X, Y, W, Z \} \hspace{0.2cm}

V_T = \Sigma = \{a, b\}

Set of Production rules P:

$S \rightarrow XY \hspace{0.2cm} | \hspace{0.2cm} W$

$X \rightarrow aXb \hspace{0.2cm} | \hspace{0.2cm} \epsilon$

$Y \rightarrow cY \hspace{0.2cm} | \hspace{0.2cm} \epsilon$

$W \rightarrow aWc \hspace{0.2cm} | \hspace{0.2cm} Z$

$Z \rightarrow bZ \hspace{0.2cm} | \hspace{0.2cm} \epsilon$

Solutions L3

L_3, Generate language with alternating a's and b's

V_N = \{ S,A,B\} \hspace{0.2cm}

V_T = \Sigma_1 = \{a, b\}

$S \rightarrow bB\hspace{0.2cm}|\hspace{0.2cm}aA\hspace{0.2cm}|\hspace{0.2cm}\epsilon$

$A \rightarrow bB\hspace{0.2cm}|\hspace{0.2cm} \epsilon$

$B \rightarrow aA\hspace{0.2cm}|\hspace{0.2cm} \epsilon$

Solutions L4

L_4 = \{a^nb^nc^m \mid n,m>0\} \cup \{a^nb^mc^m \mid n,m>0\}

V_N = \{S,M,N,A,C\}

V_T = \Sigma = \{a,b,c\}

$S \rightarrow aNbC\hspace{0.2cm}|AbMc$

$N \rightarrow aNb\hspace{0.2cm}| \hspace{0.2cm}\epsilon$

$M \rightarrow bMc\hspace{0.2cm}| \hspace{0.2cm}\epsilon$

$C \rightarrow cC\hspace{0.2cm}|\hspace{0.2cm}\epsilon$

$A \rightarrow aA\hspace{0.2cm}|\hspace{0.2cm} \epsilon$

Context-Sensitive grammars (type 1) #

The rules of the form $\alpha A \beta \rightarrow \alpha \gamma \beta$ , where $A$ is a non-terminal and $\alpha$ , $\beta$ and $\gamma$ are strings of terminals and non-terminals.

$\gamma$ must be non-empty
The rule $S\rightarrow\epsilon$ is allowed if S does not appear on the right side of any rule

Example #
Generate language:
$\{A^nB^nC^n | n > 0\}$
Set of production rules: #
$S \rightarrow aBC$
$S \rightarrow aSBC$
$CB \rightarrow CZ$
$CZ \rightarrow BZ$
$BZ \rightarrow BC$
$aB \rightarrow ab$
$bB \rightarrow bb$
$bC \rightarrow bc$
$cC \rightarrow cc$

Exercises #
Define context-sensitive grammars that produce the following languages:
$L_1 = \{a^ib^jc^id^j \hspace{0.2cm}|\hspace{0.2cm} i,j \geq 1\}$
$L_2 = \{WW \hspace{0.2cm}|\hspace{0.2cm} W ∈ \{a, b\}^∗\}$
Homework:
$L_3 = \{W ∈ \{a, b, c\}^∗| \#(a) = \#(b) = \#(c) and \#(a) ≥1 \}$

Solutions #

Solutions

Solutions L1

L_1 = \{a^ib^jc^id^j \hspace{0.2cm}|\hspace{0.2cm} i,j \geq 1\}

V_N = \{S,X,B,C, Y,Z\}; \hspace{0.2cm}

V_T = \Sigma = \{a,b\}

Set of Production rules P:

$S \rightarrow XY$

$X \rightarrow aXC\hspace{0.2cm} |\hspace{0.2cm} aC$

$Y \rightarrow BYd\hspace{0.2cm} | \hspace{0.2cm}Bd$

$CB \rightarrow CZ$

$CZ \rightarrow BZ$

$BZ \rightarrow BC$

$aB \rightarrow ab$

$Cd\rightarrow cd$

Solutions L2.1

L_2= \{WW \hspace{0.2cm}|\hspace{0.2cm} W ∈ \{a, b\}^∗\}

V_N = \{S, A, B, C, D, E\} \hspace{0.2cm}

V_T = \Sigma = \{a, b\}

Set of Production rules P:

$S \rightarrow \epsilon \hspace{0.2cm}| \hspace{0.2cm}CD\hspace{0.2cm}|\hspace{0.2cm} EF$

$C \rightarrow aCA \hspace{0.2cm}|\hspace{0.2cm} bCB \hspace{0.2cm}|\hspace{0.2cm} a$

$D \rightarrow aEA \hspace{0.2cm}|\hspace{0.2cm} bEB \hspace{0.2cm}| \hspace{0.2cm}b$

$AD \rightarrow XD$

$BD \rightarrow YD$

$AF \rightarrow XF$

$BF \rightarrow YF$

$AX \rightarrow VX$

$VX \rightarrow VW$

$VW \rightarrow VA$

$VA \rightarrow XA$

$BX \rightarrow WX$

$WX \rightarrow WV$

Continue..on next slide

Solutions L2.2

L_1 = \{WW \hspace{0.2cm}|\hspace{0.2cm} W ∈ \{a, b\}^∗\}

V_N = \{S, A, B, C, D, E\} \hspace{0.2cm}

V_T = \Sigma = \{a, b\}

Set of Production rules P:

$WV \rightarrow WB$

$WB \rightarrow XB$

$AY \rightarrow UY$

$UY \rightarrow UZ$

$UZ \rightarrow UA$

$UA \rightarrow YA$

$BY \rightarrow ZY$

$ZY \rightarrow ZU$

$ZU \rightarrow ZB$

$ZB \rightarrow YB$

$aD \rightarrow aa$

$bD \rightarrow ba$

$aF \rightarrow ab$

$bF \rightarrow bb$

$aX \rightarrow aa$

$bX \rightarrow ba$

$aY \rightarrow ab$

$bY \rightarrow bb$

Solution L3

L_{3}=\left\{w \mid w \in\{a, b, c\}^{*} \wedge \#(a)=\#(b)=\#(c) \geq 1\right\}

V_N = \{S,A,B,C,P,Q,R,X,Y,Z\}

V_T = \Sigma = \{a, b, c\}

Set of Production rules P:

$S \rightarrow SABC\hspace{0.2cm}|\hspace{0.2cm}ABC$

$A\rightarrow a$

$AB\rightarrow AQ$

$AQ \rightarrow BQ$

$BQ \rightarrow BA$

$AC \rightarrow AR$

$AR \rightarrow CR$

$CR \rightarrow CA$

$B \rightarrow b$

$BA \rightarrow BP$

$BP \rightarrow AP$

$AP \rightarrow AB$

$BC \rightarrow CZ$

$BZ \rightarrow CZ$

$CZ \rightarrow CB$

$C \rightarrow c$

$CA \rightarrow CX$

$CX \rightarrow AX$

$AX \rightarrow AC$

$CB \rightarrow CY$

$CY \rightarrow BY$

$BY \rightarrow BC$

Unrestricted grammars (type 0) #

The rules of the form $\alpha \rightarrow \beta$ , where $\alpha$ and $\beta$ are strings of non-terminals and terminals.

The grammars without any limitation on production rules.
$\alpha$ at least have one non-terminal
$\alpha$ cannot be an empty string

Example: #
Generate language:
$\{A^nB^nC^n | n > 0\}$
Set of productions rules: #
$S \rightarrow aBC$
$S \rightarrow aSBC$
$CB \rightarrow BC$
$aB \rightarrow ab$
$bB \rightarrow bb$
$bC \rightarrow bc$
$cC \rightarrow cc$

Exercises #

Generate Unrestricted grammars for below languages:

$L_1 = \{W | W = a^i$ and $i = 2^ k$ and $k > 0\}$
$L_2 = \{a^nb^mc^nd^m \hspace{0.2cm}|\hspace{0.2cm} n>0, m>0\}$

Solutions #

Solutions

Solution L1

L_1 = \{W : W = a^i and i = 2^ k and k > 0\}

V_N = \{S, L, X, Y\};

V_T = \Sigma = \{a, b, c\}

Set of Production rules P:

$S \rightarrow LaaYR$

$aX \rightarrow Xaa$

$LX \rightarrow LY \hspace{0.2cm}|\hspace{0.2cm} \epsilon$

$L \rightarrow \epsilon$

$Ya \rightarrow aaY$

$YR \rightarrow XR \hspace{0.2cm}|\hspace{0.2cm} \epsilon$

$R \rightarrow \epsilon$

Solution L2

L_2=\{a^nb^mc^nd^m \hspace{0.2cm}|\hspace{0.2cm} n>0, m>0\}

V_N = \{S, A, B, C, X, Y\};

V_T = \Sigma = \{a, b, c\}

Set of Production rules P:

$S\rightarrow XY$

$X\rightarrow aXC\hspace{0.2cm}|\hspace{0.2cm}aC$

$Y\rightarrow BYd \hspace{0.2cm}| \hspace{0.2cm} Bd$

$CB\rightarrow BC$

$aB\rightarrow ab$

$bB\rightarrow bb$

$Cd\rightarrow cd$

$Cc\rightarrow cc$

Homework: #

$L_3 = \{ a^n b^{2n}c^{3n} \hspace{0.2cm}| \hspace{0.2cm} n ≥ 1\}$