Composing Automata

--- tags: compiler construction, algorithm analysis --- $\newcommand{\sem}[1]{[\![#1]\!]}$ (part of Algorithm Analysis 2023) ("the book" or [IATLC] refers to Introduction to Automata Theory, Languages, and Computation) (there is a part 2 "Regular Expressions") # Composing Automata Earlier in the course, we studied DFAs as a domain specific language for algorithms accepting a formal language. An application of this are algorithms searching for a pattern in text. Here we will learn why such search is called regular expression (or regexp) search. As the patterns get more complicated and the automata bigger, the automata themselves are 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? (On the way, we will (re)discover NFAs and NFAs with so-called epsilon transitions.) The answer to the question arises from thinking about composition of 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 make a quick detour specifying the semantics of DFAs in terms of formal languages (recall that a formal language (and we will drop "formal" in the following) is simply a set of words without assuming any additional structure.) ## Denotational Semantics of DFAs Earlier in the course, we used automata to describe languages, that is, sets of words. We will now formalise this connection between DFAs and languages. Recall that $\Sigma^\ast$ is the set of all words 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 extended $\delta$ from input symbols in $\Sigma$ to words in $\Sigma^\ast$ $$\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, $2=\{0,1\}$) $$\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$**. The details of the following remark are not important. But it is important to know that the above mathematical definitions can be easily implemented. Moreover, in a programming language such as Haskell, the program and the mathematical definition are identical, up to changing some names and fonts. For example, the remark below makes use of the following table, for more details recall our [Short Introduction to Automata (Written in Haskell)](https://hackmd.io/@alexhkurz/HylLKujCP). |Mathematics|Programming| |:---:|:---:| $Q$ | `State` $\Sigma$ | `Char` $\Sigma^\ast$ | `[Char]` $\delta$ | `delta` $\hat\delta$ | `run delta` $\epsilon$ | `[]` $2$ | `Bool` $\sem{-}$ | `semantics` **Remark:** Recall from [automata01](https://repl.it/@alexhkurz/automata01#main.hs) of our [Short Introduction to Automata (Written in Haskell)](https://hackmd.io/@alexhkurz/HylLKujCP) 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. More precisely, a language $L$ is regular if there is a DFA $A$ such that $L=\sem{A}$. 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 and the next lecture would be (see Chapter 3 of [IATLC]): # Regular Expressions and Languages ## 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 (like floor boards), but also involves some communication between components. 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 simple but nevertheless has a rich structure. Moreover, it is a 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$ (These are the most important operations on automata, but there are others such as a synchronized parallel composition or reversal or projection, to name but a few.) In order to achieve this, we will use - that NFAs and DFAs are equivalent (some of the constructions are easier for NFAs) and - that NFAs can be extended by so-called epsilon transitions. In this lecture we will not study the algorithm that eliminates epsilon-transitions but assume that we have one at our disposal. And we already have seen an algorithm for turning an NFA into a DFA. ## 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. In this lecture we formalise tasks as languages (as we have done when we discussed decidability, P vs NP, PSPACE). 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 (needed for the next lecture) **Homework:** Write down a diagram for each of the following: - a DFA (denoted by $A_\varnothing$) that accepts the empty language $\{\}$, - a DFA (denoted by $A_\epsilon$) that accepts only the empty word, that is, the language $\{\epsilon\}$, - a DFA (denoted by $A_a$) that accepts only a single letter `a`, that is, the language $\{a\}$. How would you specify the same languages using NFAs? ## Homework for the Report Repeat from the lecture the pictorial definitions of the following operations on automata - $A_1 \mid A_2$ - $A_1 \,; A_2$ - $A^\ast$ and illustrate them with your own examples (in particular, you need to write out automata for $A$, $A_1$ and $A_2$). Also describe the languages accepted by these automata, and (after the next lecture) give the corresponding regular expressions. Choose automata and languages that are simple but illustrate the interesting features. ## <font color=black>Homework (optional) This homework is optional, but important for a deeper understanding of the material. Revision from Week 2: - Read Section 2.3.2. Most importantly, the definition of an NFA on page 57. In particular note ![](https://i.imgur.com/H92kg6L.png) Definition of NFA with epsilon transitions: - Read Section 2.5.2. Most importantly, the definition of an $\epsilon$-NFA. Exercises: - 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) </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$.)