RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Pages

ε-nondeterministic finite automata

Overview

An ε-nondeterministic finite automaton (ε-NFA for short) is another tool that can be used to recognize strings as part of a regular language.

Example of an ε-NFA

The following is an example of an ε-NFA:

Example ε-NFA. This ε-NFA containers 6 states - s0, s1, s2, s3, s4 and s5. s0 transitions to s1 on input string a. s1 transitions to s2 and s4 on input symbol ε s2 transitions to s3 on input symbol b. s4 transitions to s5 on input symbol b.

It contains 6 states and 5 state transitions.

State s0 is the initial state, while s3 and s5 are accepting states.

State s1 illustrates a construction that is not allowed in an NFA but is allowed in an ε-NFA: transitions with ε as input. These ε transitions do not consume an input symbol.

This ε-NFA accepts the language represented by the following regular expression:

a(b ∪ c)

Anatomy

In general, an ε-NFA consists of:

  1. A set of states, S, typically labelled s0 through sn - 1
    1. One state is the initial state, si - typically s0 by convention
    2. Any number of states can belong to the set of final states, Sf
      1. Sf ⊆ S
  2. A set of transitions, T, between states, consisting of a start state ss ∈ S, an end state sf ∈ S and a transition symbol t ∈ Z ∪ {ε}
    1. This differs from NFAs which don't allow ε as an input symbol for transitions

In an ε-NFA, we have essentially no inherent structural restrictions, with the following key notes about its construction:

  1. T = T[si, t] = {sf1, sf2, ..., sfn}, a set of states
  2. t ∈ Z ∪ {ε}, a single symbol in our alphabet or the empty symbol

The ε-NFA parsing algorithm

To determine whether s = {σ1σ2...σn} belongs to the language recognized by ε-NFA with states S, transitions T[si, t], initial state si:

Set Scurrent = {si} While some state sεnext is reachable through ε transition from some state sεcurrent in Scurrent such that sεnext ∉ Scurrent Add sεnext to Scurrent For i = 1 to n symbol = σi Snext = {} For each scurrent in Scurrent snext = T[scurrent, symbol] If snext exists Add snext to Snext While some state sεnext is reachable through ε transition from some state sεcurrent in Snext such that sεnext ∉ Scurrent Add sεnext to Snext If Snext is empty Reject Scurrent = Snext End for If Scurrent contains an accepting state Accept Otherwise Reject

Informally, we perform the NFA parsing algorithm but in addition, whenever a state is added to a set we are considering, we also add all states reachable directly or indirectly through ε transitions from it.

Note that this parsing algorithm is becoming somewhat complicated and is not often used in practice. We will later show how to reduce ε-NFAs into NFAs and then DFAs to simplify the parsing algorithm.

Parsing examples

Example

For s = a

States Input symbol Action
{s0} a Transition to {s1, s2, s4} (since s2 and s4 are reachable via ε transition)
{s1, s2, s4} $ (end of string) Reject (since Scurrent does not contain an accepting state)

Example

For s = ab

States Input symbol Action
{s0} a Transition to {s1, s2, s4} (since s2 and s4 are reachable via ε transition)
{s1, s2, s4} b Transition to {s3}
{s3} $ (end of string) Accept (since Scurrent contain s3 which is an accepting state)

GitHub Repository: https://github.com/bprollinson/ripal

Copyright © 2017 Brendan Rollinson-Lorimer