Quiz 1: Grammars and Languages

Set Problems Posted
Solution posted
20 Jan 30 Jan
  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?