Quiz 1: Grammars and Languages

Quiz Posted
(Thursdays)
Given in class
(Thursdays)
10 Jan 17 Jan
[an error occurred while processing this directive]
  1. Provide a context-free grammar for each of the following languages:
    1. The set of strings of base-8 numbers.
    2. The set of strings of base-16 numbers.
    3. The set of strings of base-1 numbers.
  2. Design a language that allows specification of strings of base-1, base-8, and base-16 numbers, where numbers of a given type can be syntactically distinguished. Provide a grammar for this language.
  3. Show a derivation of
                 ( Plus ( Plus a a ) a )
    
    using the grammar:
      E ->  ( Plus  E E )
        |   ( Minus E E )
        |   a
    
  4. Show all distinct derivations (trees) of
              a + a + a
    
    using the grammar:
      E ->  E + E
        |   a
    
  5. For the grammar below, describe its associated language:
       A ->  x A x
         |   lambda
    
  6. What are the difficulties associated with constructing a grammar whose generated strings are decimal representations of irrational numbers? How can these difficulties be resolved?