Composing Automata

$\newcommand{\sem}[1]{[\![#1]\!]}$ (part of [CC 22](https://github.com/alexhkurz/compiler-construction-2022/blob/master/lecture-by-lecture.md)) ("the book" refers to [Introduction to Automata Theory, Languages, and Computation](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20%282006%29.pdf)) # Composing Automata Previously: Lectures 1.1 and 1.2 In the first week we studied DFAs as a programming language independent specification language for algorithms searching for a pattern in text. This week we will learn why this is called regular expression (or regexp) search. We have already seen that as the patterns get more complicated and the automata bigger, they are themselves in need of a specification language of their own. Let us pretend we didn't know yet about regular expressions. How could we discover a specification language for DFAs? The answer to the question arises from thinking about composing automata. How should we compose larger automata from smaller ones? What are systematic ways of doing this? How should we design a domain specific language (DSL) to describe such compositions? Before we answer these questions, we link them up with some ideas we have seen in Programming Languages. ## Denotational Semantics of DFAs Last week, we used automata to describe languages, that is, sets of words. For example, Question 2 of the first homework, asked you to define a DFA which recognizes the set of all words that start contain the string `abc` and end with the string `cba`. We will now formalise this connection between DFAs and languages. Recall that $\Sigma^\ast$ is the set of all words over built from symbols in $\Sigma$. **Definition:** Given an alphabet $\Sigma$ a **language** $L$ over $\Sigma$ is a subset $L\subseteq \Sigma^\ast$. Recall that given a DFA $A=(Q,\Sigma,\delta,q_0,F)$ with transition function $$\delta: Q\times \Sigma \to Q$$ we defined its extension from input symbols to words $$\hat\delta : Q\times \Sigma^\ast\to Q.$$ **Definition:** Given a DFA with transition function $\delta: Q\times \Sigma \to Q$ and set $F$ of final states, its denotational semantics (we write here $2$ for the set of Booleans) $$\sem{-}:Q\to (\Sigma^\ast\to 2)$$ is defined by $\sem{q} = \{w\mid \hat\delta(q,w)\in F\}$. We can now define the semantics of an automaton $A$ as $$\sem A = \sem{q_0}$$ To summarize, read $\sem A$ as **the language of $A$**. **Remark:** Recall first from [automata01](https://repl.it/@alexhkurz/automata01#main.hs) the Haskell definition ```haskell run :: (State -> Char -> State) -> State -> [Char] -> State run delta q [] = q run delta q (c:cs) = run delta (delta q c) cs ``` The mathematical function $\sem{-}$ can now be defined as ```haskell semantics :: State -> ([Char] -> Bool) semantics q w = final (run delta q w) ``` **Remark:** Not all languages arise as languages of DFAs. Those that do are of particular importance and are called regular. **Definition:** A language is called **regular** if it is the language of a DFA. To summarize, we have formalised our intution that languages are the meaning of DFAs. In the following we will see the important role played by switching between automata and languages. From the point of view of languages, an alternative title of this lecture would be (see Chapter 3 of [Introduction to Automata Theory, Languages, and Computation](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20%282006%29.pdf) if you are interested in more on this): ## Introduction Compositionality is one of the most important engineering principles. Remember questions from primary school such as the following. Suppose it takes 6 screws to fix a board to the floor and it takes 40 boards to lay out the floor, how many screws do you need? There is a simple formula to answer this question and this formula is an instance of the principle of compositionality: When adding floor boards, we also add the corresponding number of screws. Of course, compositionality gets more interesting and difficult when adding components consists not in merely putting them side by side, but also involves some communication between them. In fact, much of computer science and software engineering can be seen as studying different ways to compose systems. In this lecture, we will see an example that is on the one hand simple but nevertheless has a rich structure. Moreover, composing automata is in many ways the paradigmatic example that has been influencing all areas of computer science. **The Challenge of Compositionality:** Suppose we have a task $T$ that can be split in smaller tasks $T_i$ each solved by a DFA $A_i$, is there a way to compose the DFAs $A_i$ to a DFA $A$ that solves $T$? ## Aims Given DFAs $A_1, A_2$ learn how to construct - the negation of $A_1$ - the sequential composition of $A_1$ and $A_2$ - the asynchronous parallel composition of $A_1$ and $A_2$ - the Kleene star $A_1^\ast$ This are the most important operations on automata, but there are others such as a synchronized parallel composition or reversal or projection. In order to achieve this, we will use - that NFAs and DFAs are equivalent (some of the constructions above are easier for NFAs) and - that NFAs can be extended by so-called epsilon transitions. We will study algorithms that eliminate epsilon-transitions and that turn an NFA to a DFA in the next lecture. ## Composing Automata We talked about automata solving certains tasks. Automata are a versatile software engineering method that can be adapted to a wide variety of tasks. But in the context of a compiler construction course, it makes sense to formalise tasks as languages. For us here, the task of a automaton is to accept a given a language (or, equivalently, to generate all words in that language). **Activity:** Given DFAs $A,A_1, A_2$ accepting, respectively, languages $L,L_1, L_2$, we want to construct 1. the complelemnt-automaton $A^c$ of $A$ accepting the complement $L_1^c= \{w \mid w\notin L_1\}$, that is, $A^c$ satisfies the specification $$\sem{A^c}=\sem A^c$$ 2. the sequential composition $A_1\,; A_2$ of automata accepting the sequential composition $L_1\cdot L_2 = \{wv\mid w\in L_1, v\in L_2\}$ of languages, that is, $A_1\,; A_2$ satisfies the specification $$\sem{A_1\,; A_2}=\sem{A_1}\cdot\sem{A_1}$$ 3. the asynchronous parallel composition $A_1 \mid A_2$ of automata accepting $L_1\cup L_2 = \{w\mid w\in L_1 \textrm{ or } w\in L_2\}$, that is, $A_1 \mid A_2$ satisfies the specification $$\sem{A_1\mid A_2}=\sem{A_1}\cup\sem{A_1}$$ 4. the Kleene star $A^\ast$ accepting $L^\ast$, where for any set $L\subseteq \Sigma^\ast$ we define $L^\ast=\bigcup_{n=0}^{\infty} L^n$ with $L^n$ defined recursively via [^repetition] $L^0=\{\epsilon\}$ and $L^{n+1}=L^n\cdot L,$ that is, $A^\ast$ satisfies the specification $$\sem{A^\ast}=\sem A^\ast$$ [Hint: An $\epsilon$-transition is a transition between two states that can be taken (non-deterministically) without reading a letter from the input. Whenever convenient use $\epsilon$-transitions and the fact that $\epsilon$-transitions can be eliminated and that the resulting NFAs can be turned into equivalent DFAs. ] We will see later that all DFAs can be built using (a subset of) the constructions above from some very simple basic automata: ## Homework **Homework:** Write down - a DFA $A_\varnothing$ that accepts the empty language $\{\}$, - a DFA $A_\epsilon$ that accepts only the empty word, that is, the language $\{\epsilon\}$, - a DFA $A_a$ that accepts only a single letter `a`, that is, the language $\{a\}$. How would you specify the same languages using NFAs? Can you repeat from the lecture the pictorial definitions of the following operations on automata? - $A_1 \mid A_2$ - $A_1 \,; A_2$ - $A^\ast$ If anything in my lecture was not clear, have a look at Section 4.2.1. "Closure Properties of Regular Languages under Boolean Operations" in [the book](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20%282006%29.pdf) and ask your question on the discussion forum. **Homework:** From the [the book](http://ce.sharif.edu/courses/94-95/1/ce414-2/resources/root/Text%20Books/Automata/John%20E.%20Hopcroft,%20Rajeev%20Motwani,%20Jeffrey%20D.%20Ullman-Introduction%20to%20Automata%20Theory,%20Languages,%20and%20Computations-Prentice%20Hall%20%282006%29.pdf): - Read Section 2.3.2. Most importantly, the definition of an NFA on page 57. In particular note ![](https://i.imgur.com/H92kg6L.png) - Read Section 2.5.2. Most importantly, the definition of an $\epsilon$-NFA. ## <font color=red>Assessed Homework for the report, Deadline Sunday - Exercise 2.3.4 (p.66): Find NFAs that recognise: ![](https://i.imgur.com/9OWJ285.png) - Exercise 2.5.3 (p.79): Find $\epsilon$-NFAs that recognise: ![](https://i.imgur.com/UkHngTK.png) ![](https://i.imgur.com/N4xJYMv.png) Submit your answers as last time, via email with a link to the pdf on git. Do not make a copy of last week's report, keep adding to the same document (git keeps all versions). </font> ## Homework (Optional) Can you explain why our construction for the negation (or complement) of an automaton requires the automaton to be a DFA? What may go wrong for an NFA? Do the other constructions work equally well for DFA, NFA and $\epsilon$-NFA? ## Summary For the next lecture, in which we show how to translate regular expressions into automata, we need to remember the definitions of following notation for automata - $A_\varnothing$ - $A_\epsilon$ - $A_a$ - $A_1 \mid A_2$ - $A_1 \,; A_2$ - $A^\ast$ as well as the corresponding notation for languages - $\{\}$ - $\{\epsilon\}$ - $\{a\}$ - $L_1 \cup L_2$ - $L_1 \cdot L_2$ - $L^\ast$ [^repetition]: This recursive definition is a finite way of writing (without using "$\dots$") $$L^n = \{w_1\ldots w_n \mid w_i\in L \ \textrm{ for all } 1\le i\le n\}$$ (Recall that $w_1\ldots w_n$ stands for the concatenation of the words $w_1,\ldots, w_n$.)