Finite Automata, Regular Expressions

Support/Figures/Pasted image 20250608141556.png

Automaton

An automaton $M$ is a directed multi-graph $G_{M}$ where $V (G_{M}) = {q_{1}, q_{2}, \dots q_{n}}$ are the states, $q_{1}$ is the start state, $q_{n}$ is the accepting state, and $A d j^{+} (q_{i}) = {q_{j}^{0}, q_{k}^{1}}$ that is, every node has exactly two outgoing edges, one labelled 0 and one labelled 1. The edges are also called transitions.

Consider the above picture of an automaton $M_{1}$ . consider feeding it a string $’0110’$ . Now, read the string left to right, and follow the labelled transitions starting at q1.
q1, 0 we stay at q1
q1, 1 we go to q2
q2, 1 we go to q3
q3 is accepting state so we are done. the string $’0110’$ is accepted by $M_{1}$
Notice that $M_{1}$ only accepts strings that have two consecutive ones in them.

Language of an automaton

Let $M$ be a automaton.The set $A = {w \in B I N : w is accepted by M}$ where $w$ is a binary string, (denoted $B I N$ ). or we say that $A$ is recognised by $M$ . or $A = L (M_{1})$

Automaton Formal

An automaton $M$ is a 5-tuple $(Q, Σ, δ, q_{0}, F)$ .
$Q$ is a finite set of states.
$Σ$ finite set of alphabet symbols
$δ : Q \times Σ \to Q$ the transition function. $δ (q, a) = q^{'}$ means that if you're in state $q$ and read alphabet character $a$ you go to state $q^{'}$
$q_{0}$ is the start state, $F \subset Q$ is a finite (possible empty) set of accepting states.

A string is a finite sequence in $Σ$ . A language is a set of strings the automaton accepts.
$M$ accepts string $w =< w_{i} >^{n}$ if

$r_{0} = q_{0}$ we start at the start state
inductively, $r_{i} = δ (r_{i - 1}, w_{i})$ for each $i$
$r_{n} \in F$ , the last state is one of the accepting states.

A language $L$ in general might just be finite strings of some alphabet. a language $L$ is regular iff (defined) there exists some automaton $M$ that accepts it/recognizes it as defined above.

regular operations

let $A, B$ be languages

union $A \cup B$ , concat $A B$ , star $A^{*} = {x_{1} x_{2} . . x_{k} : x_{i} \in A, k \geq 0}$ so star is concatinating all possible sequences of strings in A of finite lengths. $A^{*}$ is countable infinite and contains the empty string, given that $A$ isn't the empty language or

Using the atomics: the set of alphabet $Σ$ , singleton subsets (written without braces) of $Σ$ , $\emptyset$ the empty language, $e$ the empty string.

So $Σ = {0, 1}$ suppose.

$(0 \cup 1)^{*} = Σ^{*}$ which is all possible binary strings of finite length.

$Σ^{*} 1$ are all possible binary strings that end with 1.

$Σ^{*} 11 Σ^{*}$ are all possible binary strings that contain 11 which is $L (M_{1})$ from the picture at the top.

Finite automaton are equivalent to regular expressions!

if you build a regular expression out of the atomics and the three oprations : union, concat and star, The set that the regular expression is, is a set of strings, and there will be an automaton that accepts EXACTLY those set of strings!

Closure properties of regular languages

If $A_{1}, A_{2}$ are regular languages, then $A_{1} \cup A_{2}$ is a regular language. (if they are over the same set of alphabet, but that doesn't need to be it still holds)

$* p r o o f * :$ Suppose $M_{1} = (Q, Σ, q_{0}, δ, F)$ and $M_{2} = (P, Σ, p_{0}, γ, E)$
$L (M_{1}) = A_{1}$ , $L (M_{2}) = A_{2}$ .

Build $$M = (Q \times P, \Sigma, (q_{0} \times p_{0}), \Delta((q_{i},p_{j}),a) := (\delta(q_{i},a), \gamma(p_{j},a)), \mathbb F := (F\times P) \cup (E \times Q)$$

$M$ is the automata that accepts a string $w$ if and only if $w \in A_{1}$ or $w \in A_{2}$

Well why? our states are like a table of states from both automata.
suppose $w \in A_{1}$ then by definition of $M$ , our start state is in the row of $q_{0}$ and is equal to $(q_{0}, p_{0})$ and by definition of our new transition function $Δ$ , the characters of $w$ will at least be in the same row of states, as the states that it would traverse in $M_{1}$ . Our new definition accepts all states whose row state is accepted by $M_{1}$ . so $w$ gets accepted by $M$ as well.

Equivalently for $w \in A_{2}$ .
$◻$