08/31 - Deterministic Finite Automata 2.1-2.2

Question 1

What is a Finite Automation

Answer 1

A Finite Automation is a 5 -tuple M = (Q, Σ, δ, q, F ), where

1. Q is a finite set, whose elements are called states,
2. Σ is a finite set, called the alphabet; the elements of Σ are called symbols,
3. δ : Q × Σ → Q is a function, called the transition function,
4. q is an element of Q; it is called the start state,
5. F is a subset of Q; the elements of F are called accept states.

Question 2

Transition function δ

Answer 2

You can think of the transition function δ as being the “program” of the finite automaton M = (Q, Σ, δ, q, F ). This function tells us what M can do in “one step”:

•Let r be a state of Q and let a be a symbol of the alphabet Σ. If the finite automaton M is in state r and reads the symbol a, then it switches from state r to state δ(r, a). (In fact, δ(r, a) may be equal to r.)

Question 3

Definition 2.2.2

Answer 3

Let M = (Q, Σ, δ, q, F ) be a finite automaton and let
w = w_1w_2 …w_n be a string over Σ. Define the sequence r_0,r_1,…,r_n of states, in the following way:
• r_0 = q,
• r_i+1 = δ(r_i,w_i+1), for i = 0, 1, …, n−1.
1. If r_n ∈ F, then we say that M accepts w.
2. If r_n ̸∈ F, then we say that M rejects w.

In this definition, w may be the empty string, which we denote by Ee, and whose length is zero; thus in the definition above, n = 0. In this case, the sequence r0,r1,…,rn of states has length one; it consists of just the state r0 = q. The empty string is accepted by M if and only if the start state q belongs to F.

Question 4

Definition 2.2.3

Answer 4

Let M = (Q,Σ,δ,q,F) be a finite automaton. The language L(M) accepted by M is defined to be the set of all strings that are accepted by M:
L(M)={w: w is a string over Σ and M accepts w}.

Question 5

Definition 2.2.4

Answer 5

a language A is called regular, if there exists a finite automaton M such that A = L(M).