Context Free Grammars(CFG)-

Derivations, Parse trees and Ambiguous grammar

Department of Computer Science and Engineering

S R K R Engineering College,

Bhimavaram-543204

K V S S R Murthy

Assistant Professor

Formal Languages and Automata Theory

Context Free Languages--Examples

Determine the CFG for language L = { a^m bⁿ c^m+n / m, n>=1 }

​

Given CFL = { abcc, abbccc, aabccc,

aabbcccc, ---- }

S🡪 a S¹ c

=> a bc c since S¹ 🡪 bc

S => abcc and so abcc is in L (G)

To generate these strings we start with S

S🡪 aSc / a S¹ c

S¹ 🡪b S¹ c / bc

next string Derivations:

S🡪 a S¹ c

=> a b S¹ c c since S¹ 🡪 b S¹ c

=> a b bc c c since S¹ 🡪 b c

S => abbccc and so abbbcc is in L (G)

​

Context Free Languages--Examples

In a similar way remaining strings of L(G) are generated.

next string Derivations:

S 🡪 a S c

=> a a S¹ c c since S 🡪 a S c

=> aa b S¹ c cc since S¹ 🡪 b S¹ c

=> aa b bc c cc since S¹ 🡪 b c

S => aabbcccc and so aabbcccc is in L (G)

​

Context Free Languages--problems

Generate the CFG for all the strings ending with 00 or (0+1)* 00

Generate the CFG for L = { aⁱ b^j c^k / j=k }

Generate the CFG for L = { aⁱ b^j c^k / i=j }

Generate the CFG for L = { aⁱ b^j c^k / i=k ; i, j, k>=1}

Generate the CFG for L = { w ∈ {0, 1} ^* : |w|_a = |w|_b }.

Or

Generate CGF for equal number of a’s and b’s

​

Generate the CFG for all the strings starting with 00 or 00 (0+1)*

Context Free Languages--problems

Determine the CFG for the language L = { aⁿ / n >=0 } or a*

Generate the CFG for L = { aⁱ b^j c^k / j=k }

Generate the CFG for generating balanced parenthesis.

Generate the CFG for L = { a^m bⁿ / m, n >=1 }

Generate the CFG for L = { w ∈ {0, 1} ^* : |w|_a = |w|_b }.

Or

Generate CGF for equal number of a’s and b’s

​

Generate the CFG for all the (0+1) * 00 (0+1)*

Derivation and Parse tree

The process of deriving a string is called as derivation.

The geometrical representation of a derivation is called as a parse tree or derivation tree.

LMD and RMD

Definition : A left-most derivation of a sentential form (String ) is one in which always Left most variable is selected and apply one of the rule of that variable.

Definition : A Right-most derivation of a sentential form (String ) is one in which always Right most variable is selected and apply one of the rule of that variable.

LMD and RMD example

S → A | A B

A → e | a | A b | A A

B → b | b c | B c | b B

S ⇒ AB

⇒ AbB

⇒ Abb

⇒ Aabb

⇒ Aabb

⇒ aabb

Leftmost Derivation.

Always picks leftmost variable.

S ⇒ AB

⇒ AAB

⇒ aAB

⇒ aaB

⇒ aabB

⇒ aabb

​

Right most derivation.

Always picks rightmost variable.

Parse tree -- LMD

Here same string is derived using LMD and RMD so both parse trees look alike.

Parse tree - RMD

LMD and RMD example

Consider the grammar and give LMD and for string (a, a)

S → (L) / a

L → L , S / S

LMD for the string :

S🡪 ( L )

=> ( L , S ) since L🡪L , S

=> ( S, S ) since L🡪S

=> ( a, S ) since S🡪 a

=> ( a, a ) since S🡪 a

​

S => (a , a )

​

(

)

Parse Tree

LMD and RMD example

Consider the grammar and give RMD and for string (a, a)

S → (L) / a

L → L , S / S

RMD for the string :

S🡪 ( L )

=> ( L , S ) since L🡪L , S

=> ( L , a ) since S 🡪 a

=> ( S, a ) since L🡪 S

=> ( a, a ) since S🡪 a

​

S => (a , a )

​

(

)

Parse Tree

LMD and RMD problems

Consider the grammar and give LMD and RMD and for string a* a + a

S → S+S / S* S /a

Consider the grammar and give LMD and RMD and for string w = aaabbabbba

S → aB / bA

A → aS / bAA / a

B → bS / aBB / b

​

LMD and RMD problems

LMD and RMD Example

LMD and RMD problems

Consider the grammar and give LMD and RMD and for string a* a + a

S → S+S / S* S /a

Consider the grammar and give LMD and RMD and for string w = aabb

S → aB / bA

S → aS / bAA / a

B → bS / aBB / b

​

Parse trees

S → A | A B

A → e | a | A b | A A

B → b | b c | B c | b B

Derivations and parse trees are not unique

The following some derivation trees for string aabb

Ambiguous grammar

Definition. A grammar G is ambiguous if there is a word w ∈ L(G) having at least two different parse trees

Let G be CFG and w is any string, if w is having at least two different derivations, or derivation trees then the string is ambiguous and hence the grammar is ambiguous.

Ambiguous grammar

Question : Show that the following grammar is ambiguous

S🡪 S+S / S * S / a

Consider the string : a * a + a First derivation

S 🡪 S + S

=> S * S + S since S 🡪 S * S

=> a * S + S since S 🡪 a

=> a * a + S since S 🡪 a

=> a * a + a since S 🡪 a

S => a * a + a and so a * a + a is in L (G)

Consider the string : a * a + a second derivation

S 🡪 S * S

=> a * S since S 🡪 a

=> a * S + S since S 🡪 S + S

=> a * a + S since S 🡪 a

=> a * a + a since S 🡪 a

S => a * a + a and so a * a + a is in L (G)

Here the string a * a + a is having two different derivations so, we will get two different parse trees and hence the string is ambiguous and the grammar is ambiguous.

Ambiguous grammar - example

Question : Show that the following grammar is ambiguous

S🡪 S+S / S * S / a

Consider the string : a * a + a First derivation

S 🡪 S + S

=> S * S + S since S 🡪 S * S

=> a * S + S since S 🡪 a

=> a * a + S since S 🡪 a

=> a * a + a since S 🡪 a

S => a * a + a and so a * a + a is in L (G)

Parse tree

Ambiguous grammar -example

Here the string a * a + a is having two different derivations and so we have two different parse trees and hence the string is ambiguous and the grammar is ambiguous.

Consider the string : a * a + a second derivation

S 🡪 S * S

=> a * S since S 🡪 a

=> a * S + S since S 🡪 S + S

=> a * a + S since S 🡪 a

=> a * a + a since S 🡪 a

S => a * a + a and so a * a + a is in L (G)

Parse tree

Ambiguous grammar -example

Here the string 3 * 2 + 5 is having two different derivation or derivation trees and hence the string is ambiguous and the grammar is ambiguous.

Show that the following grammar is ambiguous :

Two different parse trees for 3*2+5

Ambiguous grammar -example

Here the string aabb is having two different derivation or derivation trees and hence the string is ambiguous and the grammar is ambiguous.

Show that the following grammar is ambiguous S🡪SS/ aSb / ε

Two different parse trees for aabb

Ambiguous grammar Problems

Show that the following grammar is ambiguous

S🡪 aS / Sa/ a

Show that the following grammar is ambiguous

A 🡪 AA | (A) | a for the string a(a)aa

Show that the following grammar is ambiguous

S 🡪 SS | AB , A -> Aa | a , B -> Bb | b.

​

Thanks!

Contact us:

KVSSR MURTHY

Assistant Professor,

Department of CSE,

S R K R Engineering College,

China amiram,

Bhimavaram – 534204.