MUN Computer Science 1002 - Lab 8

Automata and regular languages

Review:

• Lectures 23-25.

Vocabulary

• Recursive definitions of fractals, trees, formulas, arithmetic expressions.
• Context-free grammars, derivations, parse trees.
• O-notation, growth of functions

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.
   • Base: any binary number (that is, a sequence of 0s and 1s) is a an expression on binary numbers.
   • Recursion: if a and b are two expressions on binary numbers, then so are (a) AND (b), (a) OR (b), (a) XOR (b).
   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:
   • Base: an (empty) 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).
   • Set of all non-empty even-length strings over $\{a,b,c\}$.
   • Set of all even natural numbers (your base case should still be finite).

   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.

   • A language of all strings over $\{0, 1\}$ which end with 1.
   • A language of all strings that contain at least two 0s.

   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.

   • Give two examples of strings in the language (other than ones in subquestion below), and two examples of strings not in this language.
   • Draw parse trees to derive "000000" and "01000".

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