CSED 341: Finite Automata (Part 2)

This is the part of lecture summaries of ‘CSED341 : Automata and Formal Languages’ at POSTECH.

There are two types of Finite Automata — Deterministic Finite Automata(DFA) and Non-deterministic Finite Automata(NFA). Let’s dig in one by one.

Deterministic Finite Automata

Here’s the definition of DFA:

DFA accepts/rejects finite strings of symbols and produces a unique computation of the automaton each input string.

Just think of a transition diagram. A “unique computation” means that given one string has only one arc in each state. This will be discussed in further details later.

Quintuple of DFA

A DFA also can be represented by a quintuple (5-tuple), M = (𝑄, Σ, 𝛿,𝑞, 𝐹):

  • 𝑄 : A finite set of states
  • Σ : An input alphabet
  • 𝛿 : A transition function (𝑄 x Σ → 𝑄)
  • 𝑞 : A start state (denoted as 𝑞_0, 𝑞 ∈Q)
  • F : A set of final or accepting states (𝐹 ⊆ Q)

In transition function, it takes the start state and the input alphabet symbol. So it can be denoted like 𝛿(𝑞, 𝑎) — the state that the DFA goes to when it is in state 𝑞 and input 𝑎 is received.

Transition Diagram

We can also draw a transition diagram for DFA. As a graph representation, each node represents state and each arc represents transition function. The start state should be labeled with an arrow and the final state must be indicated by double circles.

Fig 1. Transition Diagram for DFA

One interesting trick is that you can add a dead state to make the complete DFA which covers every state on every alphabet symbol. The dead state serves as a black hole, which doesn’t let you escape.

Fig 2. Example of Dead State

We also can draw a transition table like Figure 3. It’s pretty intuitive, nothing special.

Fig 3. Transition Table for DFA

Extended Transition Function

This describes what happens when we start in any state and follow any sequence of inputs. It can be denoted as a hatted 𝛿.

Regular Language

In computer science, we now want to classify languages. We call a language regular if it can be decided if a word is in the language with an algorithm/a machine with finite memory by examining all symbols in the word one after another.

A language L is regular if and only if there exists a DFA M such that L = L(M).

What you need to do to show that L is regular, is to find a DFA M such that L = L(M). Here’s an example of proof by finding a DFA.

Fig 4. Showing the Given Language is Regular