Class: DFA

Inherits:
FiniteAutomata show all
Defined in:
lib/finite_automata.rb

Overview

A deterministic finite automaton M is a 5-tuple (Q, Sigma, delta, q0, F), consisting of

  • Q, a finite set of states

  • Sigma, a finite set of input symbols called the alphabet

  • delta, a state transition function (delta: Q x Sigma –> Q)

  • q0, a start state (q0 element Q)

  • F, a set of accept states (F subset Q)

Instance Attribute Summary

Attributes inherited from FiniteAutomata

#accepting_states, #alphabet, #start_state, #state_transitions, #states

Instance Method Summary collapse

Methods inherited from FiniteAutomata

#initialize

Constructor Details

This class inherits a constructor from FiniteAutomata

Instance Method Details

#run(word) ⇒ Object

Let M = (Q, Sigma, delta, q0, F) be a finite automaton and let w = w1w2…wn be a string where each w_i is a member of the alphabet Sigma. Then M accepts w if a sequenceo of states r0, r1, …, rn in Q exists with tree conditions:

  1. r0 = q0

  2. delta(r_i, w_(i+1)) = r_(i+1) for i = 0, …, n-1 and

  3. rn element F



49
50
51
52
53
54
55
56
 
# File 'lib/finite_automata.rb', line 49

def run(word)
	states = [@start_state]
	word.each_char do |c| 
		#puts "(#{states.last}, #{c}) --> #{@state_transitions[states.last][c.to_i]}" 
		states.push(@state_transitions[states.last][c.to_i]) 
	end
	return @accepting_states.include?(states.last)
end