10  Experiment with Finite Automata

In this chapter we suggest some resources/exercises/activities to get more familar with what can be done using \varepsilon-NFAs and DFAs. Regarding the resources available, you have the RACSO webpage and the exercises on the Problem Set 2 from the TC course main page.

Other useful exercises are the following.

Warning

I might update the list of exercises in the upcoming weeks.

Exercise 10.1 Using your favourite (or the more suitable) programming language write down a program that given as input a DFA/NFA A and a word w outputs whether w\in\mathscr{L}(A).

If you are already learning SWI-Prolog (for instance if you are attending the Logics in Information Technology course at UPC) try to do this exercise using this programming language.

Exercise 10.2 (DFAs for the length of words) Let n,k\in \mathbb N and L_{n,k}\subseteq \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* be the following language: L_{n,k}=\{w \in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|\in n\mathbb N+k\}\ .

For each of the following values of the parameters n and k, write a DFA A s.t. \mathscr{L}(A)=L_{n,k}:

  1. n=2 and k=0.
  2. n=3 and k=0.
  3. n=3 and k=1.
  4. n and k arbitrary.

Exercise 10.3 (DFAs for modular counting) Let n\in \mathbb N and L_n\subseteq \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* be the following language: L_n=\{w \in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\mathtt{value}_2(w)\in n\mathbb N\}\ .

For each of the following values of the parameter n, write a DFA A s.t. \mathscr{L}(A)=L_n:

  1. (🌱) n=2.
  2. n=3.
  3. n=4. Find an A with 3 states.
  4. n=5.
  5. n=6.
  6. n=7.
  7. n=8. Find an A with 4 states.
  8. n=2^k. Find an A with k+1 states.
  9. n\in 2\mathbb N +1.
  10. (🔥) n=2^kd with d\in 2\mathbb N+1. Find and A with k+d states.

Exercise 10.4 Write a DFA for the language \{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\binom{|w|}{2}\in 6\mathbb{N}+4\}.

Maintain both \binom{|w|}{2} \pmod{6} and |w| \pmod{6}.