MUN Computer Science 1002 - Lab 8

Automata and regular languages




Individual work

Solve each of the following exercises.

  1. Consider the following list of functions and determine, for each pair of them, which of them is in $O()$ of the other: $ 2^n, 10n^2+5, n^3, 50n$.
  2. Let a function $A$ on pairs of natural numbers be defined as follows: $A(0,n)= n+2$, $A(m, 0) = A(m-1,1)$ and $A(m,n) =A(m-1, A(m,n-1))$ for $m, n \geq 1$. This function is a variant of the famous Ackermann function, but the definition is slightly different (so the numbers would not be the same as the standard Ackermann function). Now, compute the values of $A(0,3)$, $A(1,0)$, $A(1,3)$ and $A(2,1)$.
  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 (iteration 0) and first two iterations of the following fractal:

    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$.