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\} \)