Finite Automaton

Posted By on April 29, 2016


Download PDF
Regular Expressions
Deterministic Finite Automaton

An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).

Formal definition of a Finite Automaton

An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where −

  • Q is a finite set of states.
  • is a finite set of symbols, called the alphabet of the automaton.
  • δ is the transition function.
  • q0 is the initial state from where any input is processed (q0 ∈ Q).
  • F is a set of final state/states of Q (F ⊆ Q).

Related Terminologies

Alphabet

  • Definition − An alphabet is any finite set of symbols.
  • Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are alphabets.

String

  • Definition − A string is a finite sequence of symbols taken from ∑.
  • Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c,d}

Length of a String

  • Definition − It is the number of symbols present in a string. (Denoted by |S|).
  • Examples
    • If S=‘cabcad’, |S|= 6
    • If |S|= 0, it is called an empty string (Denoted by λ or ε)

Kleene Star

  • Definition − The set * is the infinite set of all possible strings of all possible lengths over including λ.
  • Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪…….
  • Example − If ∑ = {a, b}, ∑*= {λ, a, b, aa, ab, ba, bb,………..}

Kleene Closure/Plus

  • Definition − The set + is the infinite set of all possible strings of all possible lengths over excluding λ.
  • Representation − ∑+ = ∑0 ∪ ∑1 ∪ ∑2 ∪…….

    + = ∑* − { λ }

  • Example − If ∑ = { a, b } , ∑+ ={ a, b, aa, ab, ba, bb,………..}

Language

  • Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.
  • Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}

Construction of an FA from an RE

We can use Thompson’s Construction to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and converting these to NFA and finally to DFA.

Some basic RA expressions are the following −

Case 1 − For a regular expression ‘a’, we can construct the following FA −

Finite Automata for RE

Case 2 − For a regular expression ‘ab’, we can construct the following FA −

Finite Automata for RE1

Case 3 − For a regular expression (a+b), we can construct the following FA −

Finite Automata for RE2

Case 4 − For a regular expression (a+b)*, we can construct the following FA −

Finite Automata for RE3

Method

Step 1 Construct an NFA with Null moves from the given regular expression.
Step 2 Remove Null transition from the NFA and convert it into its equivalent DFA.

Problem

Convert the following RA into its equivalent DFA − 1 (0 + 1)* 0

Solution

We will concatenate three expressions “1”, “(0 + 1)*” and “0”

NDFA with Null Transition for RA

Now we will remove the ε transitions. After we remove the εtransitions from the NDFA, we get the following −

NDFA with Null Transition for RA1

It is an NDFA corresponding to the RE: 1 (0 + 1)* 0. If you want to convert it into a DFA, simply apply the method of converting NDFA to DFA discussed in Chapter 1.

Finite Automata with Null Moves (NFA – ε)

A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a null move.

An NFA-ε is represented formally by a 5-tuple (Q, ∑, δ, q0, F), consisting of

  • Q − a finite set of states
  • − a finite set of input symbols
  • δ − a transition function δ : Q × (∑ ∪ {ε}) → 2Q
  • q0 − an initial state q0 ∈ Q
  • F − a set of final state/states of Q (F⊆Q).

Finite Automata with Null Moves

Removal of Null Moves from Finite Automata

If in an NDFA, there is ε-move between vertex X to vertex Y, we can remove it using the following steps −

  • Find all the outgoing edges from Y.
  • Copy all these edges starting from X without changing the edge labels.
  • If X is an initial state, make Y also an initial state.
  • If Y is a final state, make X also a final state.

Problem

Convert the following NFA-ε to NFA without Null move.

Finite Automata with Null Moves1

Solution

Step 1

Here the ε transition is between q1 and q2, so let q1 is Xand qf is Y.

Here the outgoing edges from qf is to qf for inputs 0 and 1.

Step 2

Now we will Copy all these edges from q1 without changing the edges from qf and get the following FA −

NDFA After Step 2

Step 3

Here q1 is an initial state, so we make qf also an initial state.

So the FA becomes −

NDFA After Step 3

Step 4

Here qf is a final state, so we make q1 also a final state.

So the FA becomes −

Final NDFA Without Null Moves

Regular Expressions
Deterministic Finite Automaton

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com