Show that each of the following grammars is ambigous. (To show that a grammar is

Question

Show that each of the following grammars is ambigous. (To show that a grammar is ambiguous, you must demonstrate that it can generate two parse trees for the same string.)

a.) The grammar G4, repeate here:

G4: <exp> : : = <exp> + <exp>

| <exp> * <exp>

| ( <exp> )

| a | b | c

b.) This grammar:

<person> : : = <woman> | <man>

<woman> : : = wilma | betty | <empty>

<man> : : = fred | barney | <empty>

c.) The following grammar for strings of balanced parentheses. (A language of any number of different kinds of balanced parentheses is called a Dyck language. This type of language plays an interesting role in the theory of foraml languages.)

<s> : : = <s> <s> | ( <s> ) | ()

d.) This grammar:

<s> : : = <round> <square> | <outer>

<round> : : = [ <square> ] | [ ]

<square> : : = ( <outer> ] | ( <inner> ]

<inner> : : = ) <inner> [ | ) [

Explanation / Answer

Ambigious:-if a grammar generates more than one parse tree then the grammar is said to be ambigious.

a.) The grammar G4, repeate here:

G4: <exp> : : = <exp> + <exp>
| <exp> * <exp>
| ( <exp> )
| a | b | c

Consider the left derivative for the grammar g4:
G4=<exp>
=<exp>+<exp> consider left derivative sub <exp> as <exp> * <exp>
=<exp> * <exp> + <exp> now substitute <exp> as ( <exp> )
=( <exp> ) * <exp>+ <exp> now substitute <exp> as a
= (a)*<exp>+<exp> now replace <exp> as b
=(a)*b+<exp> now replace <exp> as c
=(a)*b+c
therefore the G4 on left derivative gives a parse tree as (a)*b+c.if on the right derivative if it generates the same parse tree then we can say that the grammar
is ambigious
  
Consider the Right derivative for the grammar g4:
G4=<exp>
=<exp>+<exp> consider Right derivative sub <exp> as <exp> * <exp>
=<exp>+<exp>*<exp> now substitute right side <exp> with (<exp>)
=<exp>+<exp>*(<exp>) now substitute <exp> with a on the right side
=<exp>+<exp>*(a) now substitute with b on <exp>
=<exp>+b*(a) now substitute c on <exp>
=c=b*(a)

hence on the left and right derivative the grammmar derives the same parse tree hence the grammar is ambigious.
  
b.) This grammar:

<person> : : = <woman> | <man>
<woman> : : = wilma | betty | <empty>
<man> : : = fred | barney | <empty>

consider the this grammar
Left dervative:
<person>=<woman> let us substitute woman with wilma
=wilma.

<person>=<woman> let us substitute woman with betty
=betty.

<person>=<woman> let us substitute woman with empty
=<empty>.      

Right derivative:-
<person>=<man> let us substitute man with fred
=fred
      
<person>=<man> let us substitute man with barney
=barney
      
<person>=<man> let us substitute man with empty
=<empty>

       if we consider this grammar the grammar is geneating different parse trees.so the grammar is not ambigious.

c.) The following grammar for strings of balanced parentheses. (A language of any number of different kinds of balanced parentheses is called a Dyck language.

This type of language plays an interesting role in the theory of foraml languages.)
<s> : : = <s> <s>
    | ( <s> )
           | ()
          
   Consider the grammar <s> = <s> <s>
on left derivativation as :- <s> = <s> <s> on left side of <s> substitute with (<s>)
= (<s>) <s> now replace <s> with ()
                               = (()) <s> now replace <s> with ()
                               =(()) ()
   hence on left derivation the grammar gives/generates the parse tree as (()) ()
  
   on right derivation as :- <s> = <s> <s> on Right side of <s> substitute with (<s>)
                           = <s> (<s>) now replace <s> with ()
                           = <s> (()) now replace <s> with ()
                           =() (())

hence on Right derivation the grammar gives/generates the parse tree as () (()

hence the grammar is ambigious.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.