CSE 428 : Solution of Assignment #1

Question 1

   <Sentence> ::= <Subject> <Trans_Verb> <Object>
                | <Subject> <Intrans_Verb>
                | <Subject> <Neg> <Trans_Verb_Inf> <Object>
                | <Subject> <Neg> <Intrans_Verb_Inf>
                | <Aux> <Subject> <Trans_Verb_Inf> <Object> ?
                | <Aux> <Subject> <Intrans_Verb_Inf> ?
                  
   <Subject> , <Object> ::= <Article>  <Name> |  <Proper_Name>

   <Article> ::= the 

   <Name> ::= cat | milk | sun

   <Proper_Name> ::= John | Ann

   <Trans_Verb> ::= drinks | likes

   <Intrans_Verb> ::= sleeps | walks | drinks 

   <Trans_Verb_Inf> ::= drink | like

   <Intrans_Verb_Inf> ::= sleep | walk | drink

   <Neg> ::= <Aux> not

   <Aux> ::= does

Question 2

   S ::= lambda | aSb

Question 3

   S ::= lambda | aSbS | bSaS

Question 4

1. There are various ambiguities, due to
   • lack of rules for associativity of "and" and ->
   • lack of a rule of precedence between -> and "and"
   • lack of a rule of precedence between -> and "not"
   • lack of a rule of precedence between "and" and "not"
   An example of the last kind of ambiguity is the following:

             BExp                  BExp
           /  |  \                /   |  
       BExp  and  BExp         not   BExp
       /  |        |               /  |  \ 
     not BExp    false         BExp  and  BExp
          |                      |         |
        false                  false     false    
   
   

2.    BExp  ::= BTerm -> BExp | BTerm
   
      BTerm ::= BTerm and Literal | Literal
   
      Literal ::= not Literal | Atom
    
      Atom  ::= true | false
   

Question 5

   Exp  ::= Exp + Term | Exp - Term | Term	

   Term ::= Term * Factor | Term / Factor | Factor

   Factor ::= Base ^ Factor | Base

   Base ::= (Exp) | Num

   Num ::= 0 | Non_Zero_Digit Seq

   Seq ::= lambda | Digit Seq 

   Non_Zero_Digit ::= 1 | 2 | ... | 9

   Digit ::= 0 | Non_Zero_Digit