RIPAL: Responsive and Intuitive Parsing for the Analysis of Language

Overview

A deterministic finite automaton (DFA for short) is a tool that can be used to recognize strings as part of a regular language.

Example of a DFA

The following is an example of a DFA:

It contains 4 states (the circles) and 4 state transitions (the arrows between states).

State s₀ is the initial state (indicated by the arrow coming from no other state), while s₂ and s₃ are accepting states (indicated by the double circle).

This DFA accepts the language represented by the following regular expression:

R = ab ∪ acd^*

Anatomy

In general, a DFA consists of:

1. A set of states, S, typically labelled s₀ through s_{n - 1}
   1. One state is the initial state, s_i - typically s₀ by convention
   2. Any number of states can belong to the set of final states, S_f
      1. S_f ⊆ S
2. A set of transitions, T, between states, consisting of a start state s_s ∈ S, an end state s_f ∈ S and a transition symbol t ∈ Z

In a DFA, we have a few inherent structural restrictions, as follows:

1. T = T[s_i, t] = s_f, a singular state
2. t ∈ Z, a single symbol in our alphabet

The DFA parsing algorithm

To determine whether s = {σ₁σ₂...σ_n} belongs to the language recognized by DFA with states S, transitions T[s_i, t], initial state s_i:

Informally, we begin with our initial state, and transition to subsequent states for each symbol in the input.

We reject the language if we end on a non-accepting state at the end of our input or attempt an invalid transition. We accept if an accepting state is reached at end of input.

Parsing examples