Automata and regular languages

- Lectures 21, 23-25.

- O-notation, growth of functions
- Regular languages
- Deterministic and non-deterministic finite automata

Solve each of the following exercises.

- Show, using definition of $O$-notation (by finding $n_0$ and $c$), that
- $3n^2-4 \in O(n^2)$
- $n^3 \in O(3^n)$

- 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)$.
- For each of the following automata descriptions, first draw the automaton, and say whether it is deterministic or non-deterministic. Then show a sequence of states it goes through on each of the following strings: $00$, $001$, $00110110$ and the empty string. Which of these strings were accepted? And what do you think would be languages of each of these automata?
- Alphabet: {0,1}. States: $s_1, s_2, s_3$, with $s_1$ being the start state, and $s_2$ a single finish state (so $s_2$ is an accepting state, and $s_1, s_3$ are not accepting).

Transitions: $(s_1, 0) \to s_1$, $(s_1, 1) \to s_2$, $(s_2, 0) \to s_2$, $(s_2, 1) \to s_3$, $(s_3, 0) \to s_3$, $(s_3, 1) \to s_2$. - Alphabet: {0,1}. States: $s_1, s_2$, with $s_1$ being the start
state, and $s_2$ a single finish state.

Transitions: $(s_1, 0) \to s_1$, $(s_1, 1) \to s_1$, $(s_1, 1) \to s_2$, $(s_2, 0) \to s_2$.

- Alphabet: {0,1}. States: $s_1, s_2, s_3$, with $s_1$ being the start state, and $s_2$ a single finish state (so $s_2$ is an accepting state, and $s_1, s_3$ are not accepting).

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.

- A language of all strings over $\{a,b,c\}$ containing a substring "abc".
- A language of all strings over $\{0,1\}$ having 1 as a second-to-last bit (e.g, 010 and 1011 are ok, but not 001).

Recall that a finite automaton is deterministic if from every state it has exactly one outgoing edge for each letter from the alphabet. Draw deterministic finite automata accepting the following languages over {0,1} :

- A language of all strings that contain a substring "00".
- A language of all strings over $\{0, 1\}$ which end with 1.

Recall that in a non-determinisitc finite automata it is OK to have multiple edges from the same state labeled with the same label (this is interpreted as "or"), and some edges might be missing (this is interpreted as "stop and reject"). Draw non-deterministic automata for the following languages.

- A language of all strings that do not contain a substring 11 (hint: use "missing edges").
- A language of all strings that have 1 in the second-to-last bit (e.g, 010 and 1011 are ok, but not 001).

Consider the language of all strings over {0,1} that either contain a substring "00" or have a 0 in the second-to-last position.

- Write a regular expression for this language.
- Draw a 4-state non-deterministic automaton for this language (use both multiple and missing edges).
- Draw a deterministic automaton for this language (hint: start by writing a 4-state deterministic automaton for "has 0 in second-to-last position", and attach it to the automaton that detects a "00" substring).