Scribd
Upload
54 views

Formal Chapter 2

The document discusses introduction to grammars including phrase structure grammar, derivation, Backus-Naur form, syntax diagrams, and examples of grammar rules and languages generated by grammars.

Uploaded by

Ermias
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
54 views

Formal Chapter 2

The document discusses introduction to grammars including phrase structure grammar, derivation, Backus-Naur form, syntax diagrams, and examples of grammar rules and languages generated by grammars.

Uploaded by

Ermias
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

Chapter Two

Introduction to Grammars
2. Introduction to grammars:

 outline
 Introduction to grammars
 Phrase Structure Grammar and language
 Derivation

April 24, 2024 Formal Language & Automata Theory 2


 Introduction to grammars
 A formal language is a collection of strings

over ∑ with some rules known as grammars.

April 24, 2024 Formal Language & Automata Theory 3


 Grammar rules can be represented using a syntax
diagram.
 Alternatively BNF (Backus-Naur Form) notation can be
used.

Syntax Diagram
Example:
Identifier

Letter Letter

Letter

April 24, 2024 Formal Language & Automata Theory 4


Function Declaration using Syntax Diagram

type name ( variable )

April 24, 2024 Formal Language & Automata Theory 5


 BNF uses the following:
 Nonterminals : are enclosed by <>.
 Terminals are represented as they are.
 { } - represent repetition of nonterminals, terminals
zero or more times
 ::= stands for “is defined as”
 | stands for OR
 () used to group symbols

Ex.
<identifier> ::= <letter>|<letter>{<letter>|<digit>}
<letter> ::= a|b|c|…
<digit> ::= 0|1|2|…|9

April 24, 2024 Formal Language & Automata Theory 6


Intro …cont’d

Ex 1: Definition of C++ function in BNF

<funct def> ::= <type>|<name>({<parameter>})


<type> ::= int|float|double|void
<name> ::= <identifier>
<parameter>:=<type>|<type><identifier>

April 24, 2024 Formal Language & Automata Theory 7


Introduction to grammars: cont’d
 Phrase Structure Grammar (PSG)
 Definition: A PSG is a 4-tuple (N, T, P, S)

where:
a. N is a finite set of nonterminals
b. T is a finite set of terminals
c. P is a finite set of productions /rules/ of the form
αβ, where α and β are strings on N U T and α
should contain at least one symbol from N.
d. S Є N is the start symbol of the grammar.
Note: The right hand side production, β, can be
an empty string. Such a production is called a
λ-production.

April 24, 2024 Formal Language & Automata Theory 8


Intro …cont’d

 The production rules specify how to transform


one string to another
String =(T U N)*
 The production X->Y is used to replace X by

Y in the string

April 24, 2024 Formal Language & Automata Theory 9


Intro …cont’d
Ex 2. G = (N, T, P, S) = ({S, B, C}, {a, b, c}, P, S)
where P is given by:

S  aSBC | aBC
BC  CB
aB  ab
C  Cc | λ

April 24, 2024 Formal Language & Automata Theory 10


Introduction to grammars: cont’d
Derivation
 If α generates β, then we write α => β
 If α => α , α => α , …, α
1 2 2 3 n-1 => αn, then we write
α1 => α2 => α3 => … => αn or α1 => αn +
 Let G = (N, T, P, S) be a grammar, if S => α in zero or
more steps, α Є (N U T)*, then α is called a sentential
form.
 A sentence (in G) is a sentential form in T*.
 The language generated from the grammar G is
denoted by L(G).
*
L(G) = {x Є T* | S =>* x}
i.e. L(G) is the set of all terminal strings derived from
the start symbol S.

April 24, 2024 Formal Language & Automata Theory 11


Introduction to grammars: cont’d
Example of a grammar:.
G = (N, T, P, S) where:
N = {<sentence>, <noun>, <verb>, <adverb>}
T = {Sam, Dan, ate, sang, well}
S = <sentence>
P consists of:
<sentence>  <noun><verb> |
<noun><verb><adverb>
<noun>  Sam | Dan
<verb>  ate | sang
<adverb>  well

April 24, 2024 Formal Language & Automata Theory 12


Example
Let us consider the grammar −
G = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → λ } )
Some of the strings that can be derived are −
S ⇒ aAb using production S → aAb
⇒ aaAbb using production aA → aAb
⇒ aaaAbbb using production aA → aAb
⇒ aaabbb using production A → λ

April 24, 2024 Formal Language & Automata Theory 13


Example:
Suppose we have the following grammar −
G:
N = {S, A, B}
T = {a, b}
P = {S → AB, A → aA|a, B → bB|b}

The language generated by this grammar −


L(G) = {ab, a2b, ab2, a2b2, ………}
= {am bn | m ≥ 1 and n ≥ 1}

April 24, 2024 Formal Language & Automata Theory 14


Introduction to grammars: cont’d
Ex3.
S  A|B
A  aA|bB|a|b
B  bB|b

Ex4.
S  a|bS

Ex5.
S  aA|bB|a|b
A  aA|a
B  bB|b

April 24, 2024 Formal Language & Automata Theory 15


Introduction to grammars: cont’d
 Note: that reverse derivation is not permitted. For
instance, if S  AB is a production, then we can
replace S by AB, but we cannot replace AB by S.
 Notations:
i. If A is any set, then A* denotes the set of all strings
over A and A+ = A* - {λ}
ii. A, B, C, A1, A2, … denote nonterminals
iii. a, b, c, … denote terminals
iv. x, y, z, w, … denote strings of terminals
v. α, β, … denote strings from (N U T)*
vi. If A  α is a production where A Є N, the production
is called an A-production
vii. If A  α1, A  α2, A  α3, A  α4 … A  αn are all
A-productions, these can be written as A  α1| α2| α3|
α4|… αn
viii. X0 = λ for any symbol X Є N U T
April 24, 2024 Formal Language & Automata Theory 16
Introduction to grammars: cont’d
Definition: Let G1 and G2 be two grammars, then G1 and
G2 are equivalent if L(G1) = L(G2).

Ex6. G = ({S}, {a}, {S  SS|a}, S).


Find L(G)

Ex7. G = ({S, C}, {a, b}, P, S) where P is given by:


S  aCa
C  aCa | b
Find L(G)

Ex8. G = ({S}, {a}, {S  aS|a}, S).


Find L(G)

April 24, 2024 Formal Language & Automata Theory 17


Construction of a Grammar Generating a
Language
Ex:
Suppose, L (G) = {am bn | m > 0 and n ≥ 0}. We have to find
out the grammar G which produces L(G)
Solution −
Since L(G) = {am bn | m > 0 and n ≥ 0}, the set of strings
accepted can be rewritten as −
L(G) = {a, aa, ab, aaa, aab ,abb, …….}

Hence the grammar −


G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | λ| B, B → λ |
bB })
April 24, 2024 Formal Language & Automata Theory 18
Find the grammar that generates :
L={anbn+1 : n≥0}

Solution:
P:
S→aSb | b

April 24, 2024 Formal Language & Automata Theory 19


Exercise:9
Let L be the set of all palindromes over {a, b}.
Construct a grammar G that generates L.
Hint: Use the following recursive definition
i. λ is a palindrome
ii. a, b are palindromes
iii. If x is a palindrome, axa and bxb are palindromes

EX: L ={ambm+ncn | m,n>0 }


find G.

April 24, 2024 Formal Language & Automata Theory 20


Assignment

 Exercise number 6-9 will be your individual


assignment and will be submitted by next
week.

April 24, 2024 Formal Language & Automata Theory 21

You might also like