# Introduction to automata theory

## Some first examples

Automata are abstract machines modeling computations without memory. Before we get to the formal definition, let us consider some examples.

1. **Parking or vending machine:**
*Specification:* The machine asks for 25c, to be payed in chunks of 5c or 10c.

Corresponding automaton:


The state $25$ is **accepting** or **final**. A word (i.e., a concatenation of the 'symbols' $5$ and $10$) is **accepted** if it is obtained by traversing the automaton beginning at the initial state $0$ and ending at the final state $25$. E.g., the word $5\,10\,10$ is accepted while the word $10\,10\,10$ is not.

:::warning
**Exercise 1:** Characterize all the accepted words (i.e., describe exactly those words that get recognized).
:::

2. **Variable names**

Constructing a programming language, we want to define a pattern to describe valid names for a variable

*Specification:* The variable names should start with a letter ($\ell = \texttt{a}, \texttt{b}, \texttt{c},\ldots, \texttt{z}$) and can be followed by an arbitrary (but finite) number of letters ($\ell$) or digits ($d = \texttt{0}, \texttt{1}, \texttt{2},\ldots, \texttt{9}$). The end of the name is designated by a terminal symbol ($t$) (e.g. $t = \texttt{;}$.)

Corresponding automaton:

The accepted words are all of the following form:
$\ell$ followed by possibly $d$ or $\ell$, or some repetition thereof, finally stopping at $t$.

We can describe this more concisely by a **regular expression**:
$$\ell\cdot(\ell+d)^*\cdot t$$
or, for short
$$\ell(\ell+d)^*t$$

Here, the operators have the following meaning:
a. $\cdot$: concatenation
b. $+$: "or"
c. ${}^*$: "arbitrary repetition", i.e., read expression $n$-many times with $n=0,1,2,\ldots$

3. **Turnstile**

We want to model a money-operated turnstile.
*Specification:* Upon payment the turnstile unlocks. It then can be pushed so a person can pass through. It locks again after this. If you keep paying while it is open, it will stay open.

Corresponding automaton:

:::warning
**Exercise 2:** Characterize all the accepted words. Can you describe them via a regular expression?
:::

## Summary

The three graphs above are examples of **automata**. They all consist of the following:

1. nodes, called **states**
2. labeled edges, called **transitions**
3. a distinguished **starting** or **initial state**:

4. some **accepting** or **final states** (there can be multiple or just one or no accepting state; in all the cases above there is excatly one):

## Outlook

We will make this more precise soon. In due time, we will also give a formal definition of regular expressions and languages. One key result will be that the languages detected by finite automata are exactly the ones that are described by a regular expression. In that sense, finite automata correspond to regular expressions ([Kleene's](https://en.wikipedia.org/wiki/Stephen_Cole_Kleene) theorem).