Homework 4 Solutions

1. Construct context-free grammars for the following languages:

   1. The set of words with even number of a's or odd number of b's

      S -> A
      S -> C
      
      A -> aB
      A -> bA
      A -> ε
      B -> aA
      B -> bB
      
      C -> aC
      C -> bD
      D -> aD
      D -> bC
      D -> ε
      

   2. L = {aⁿb²ⁿa^mb^2m | m ≥ 1 and n ≥ 1 }

      S -> XX
      X -> aXbb
      X -> abb
      

   3. The set of words that have more a's than b's.

      S -> SA
      S -> A
      
      E -> aB
      E -> bA
      A -> bAA
      A -> aE
      A -> a
      B -> aBB
      B -> bE
      B -> b
      

2. Consider the following CFG:

   	S -> S + S
   	S -> S * S
   	S -> (S)
   	S -> a
   

   1. Give ALL possible derivations for the string a+a*a

      There are 16 different derivations.

      The following 8 use S -> S+S in the first step:

      S => S+S => a+S => a+S*S => a+a*S => a+a*a
      S => S+S => a+S => a+S*S => a+S*a => a+a*a
      
      S => S+S => S+S*S => a+S*S => a+a*S => a+a*a
      S => S+S => S+S*S => a+S*S => a+S*a => a+a*a
      
      S => S+S => S+S*S => S+a*S => a+a*S => a+a*a
      S => S+S => S+S*S => S+a*S => S+a*a => a+a*a
      
      S => S+S => S+S*S => S+S*a => a+S*a => a+a*a
      S => S+S => S+S*S => S+S*a => S+a*a => a+a*a
      

      and the following 8 use S -> S*S in the first step:

      S => S*S => S*a => S+S*a => S+a*a => a+a*a
      S => S*S => S*a => S+S*a => a+S*a => a+a*a
      
      S => S*S => S+S*S => a+S*S => a+a*S => a+a*a
      S => S*S => S+S*S => a+S*S => a+S*a => a+a*a
      
      S => S*S => S+S*S => S+a*S => a+a*S => a+a*a
      S => S*S => S+S*S => S+a*S => S+a*a => a+a*a
      
      S => S*S => S+S*S => S+S*a => a+S*a => a+a*a
      S => S*S => S+S*S => S+S*a => S+a*a => a+a*a
      

   2. What parse trees can you generate for these derivations?

      We get the following two parse trees from these 16 derivations.

      

3. Consider the following grammar for "Datalog Atoms":

   atom : NAME LPAREN args RPAREN  
     
   args : args COMMA arg  
   args : arg  
     
   arg  : NUMBER  
   arg  : STRING  
   arg  : NAME
   

   Write a "left-most" derivation for p(x,20,x,y,"john") and draw the parse tree.

   atom => p(args)
        => p(args, arg)
        => p(args, arg, arg)
        => p(args, arg, arg, arg)
        => p(args, arg, arg, arg, arg)
        => p(arg, arg, arg, arg, arg)
        => p(x, arg, arg, arg, arg)
        => p(x, 20, arg, arg, arg)
        => p(x, 20, x, arg, arg)
        => p(x, 20, x, y, arg)
        => p(x, 20, x, y, "john")
   

   Parse tree: