Review:
Vocabulary
- O-notation, growth of functions
- Regular languages
- Deterministic and non-deterministic finite automata
Individual work
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$.
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: Regular expressions
Write a regular expression for each of the languages below.
- 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).
Topic 2: Deterministic finite automata
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.
Topic 3: Non-deterministic finite automata
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).
Review after the group exercises
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).