MUN Computer Science 1002 - Lab 7

Recursive definitions




Individual work

Solve each of the following exercises.

  1. Compute the following (you can use a calculator).
    1. $\Sigma_{i=2}^5 i^2$,
    2. $ \Pi_{i=0}^3 (i+2)$
    3. $(10-6)!$
  2. List the first five elements in the following sequences.
    1. Arithmetic sequence with c=10 and d = 4.
    2. $(n!)/2^n$ for $n \in \mathbb{N}$. (Hint: define $0!=1$).
    3. $F^2_n$, $n \in \mathbb{N}$, where $F_n$ is the nth Fibonacci number.
  3. Suppose that expressions on binary numbers are defined as follows. According to this definition, which of the following are valid expressions on binary numbers?
    1. (00100) AND ( (0011) OR (11))
    2. 00011 XOR 11100
    3. (00111)
  4. Draw the base and first two iterations of the following fractals.
    1. Base: a line segment (with a direction). Recursive step: replace each line segment with
    2. Base: a square. Recursive step: Make each (empty) square a 3x3 grid (mark off 1/3 and 2/3 of each side and draw vertical and horizontal lines), and shade the middle square in the grid.

    Group exercises

    For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

    Topic 1: Recursive definitions of sets.

    Give a recursive definition of the following sets (directly, without using grammars).

    Topic 2: Grammars as recursive definitions of sets

    Recall that a (context-free) grammar consists of rules of the form $A \to w$, where $A$ is a variable, and $w$ is a string of variables and terminals (possibly empty). For each of the following languages, define a grammar that produces this language.

    Topic 3: Parse trees and derivations

    Let a language over $\{0,1\}$ be defined by the grammar $S \to S00 | 0S0 | 1 | \lambda $, where $\lambda$ is an empty string.

    Review after the group activity

    Consider the language of all palindromes over $\{a,b,c\}$ (that is, a set of all strings that read the same forwards and back).

    1. Give two examples of strings in this language, and two examples not in this language.
    2. Give a recursive definition of all palindromes over $\{a,b,c\}$. Hint: an empty string is a palindrome, and they can be even or odd length.
    3. Give a grammar generating this language.
    4. Draw parse trees for a string $aabcbaa$ and $caaaac$.