Package fsa_recognizer :: Module det_fsa_rec

[frames] | no frames]

Module det_fsa_rec

source code

This module defines a deterministic finite-state recognizer. No ε-transitions are allowed.

An FSA (here simply called a Machine) is a triple of an alphabet, a TransitionTable and a tuple of final states:

alphabet: A sequence, the elements define the set of symbols in the alphabet of Machine
TransitionTable: A list of StateTransitionFunctions
StateTransitionFunction: A dictionary whose keys are the members of the input alphabet and whose values are the states transitioned to.

Keys and values in transition functions come from the following sets:

alphabet: Must be the same for all states in a machine
states: the set of states of the machine, the first n-1 integers (including 0) for a machine of n states
undefined: the string 'und', used as the value in a StateTransitionFunction for an alphabet symbol for which the state has no defined transition.

Example machine:

>>>  Table = [{'b':1},{'a':1,'b':2,'c':0},{'a':2,'b':2}]
>>>  Finals = (0,)
>>>  Machine = ('abc', Table, Finals)

In this machine, the alphabet is {a,b,c}, and there are 3 states, 0, 1, and 2, defined by 3 StateTransitionFunctions (diagram). Lists are indexed from 0, so the state-transition function for state 2 is the 3rd in Table.

>>> get_transition_value(Table[2],'b')
2

When in state 2, transition back to state 2 upon seeing a 'b'.

>>> get_transition_value(Table[2],'c')
'und'

State 2 is undefined for the input 'c'. The FSA fails when seeing a 'c' in state 2.

Attention: a machine's state dictionaries must all be defined for the same alphabet.

Author: Jean Mark Gawron

Contact: gawron@mail.sdsu.edu

Functions

[hide private]

boolean

simple_det_recognize(machine, string)
See Jurafsky and Martin, Speech and Natural Language Processing, Fig 2.13

source code

int or 'und'

get_transition_value(transitions, symbol)
Having this function wrapper here allows some abstraction in how transition functions are implemented.

source code

int or 'und'

set_transition_value(transitions, sym, value)
Having this function wrapper here allows some abstraction in how transition functions are implemented.

source code

boolean

det_recognize(machine, string)
Differs from simple_det_recognize in printing explicit error diagnostics for failure.

source code

Machine

add_sink_state(machine)
Return a new machine just like machine but with an added sink state, k. source code

Variables

[hide private]

TransitionTable table1 = [{'b': 1}, {'a': 2}, {'a': 3}, {'!': 4, 'a': 3}, {}]
The TransitionTable for M1.

tuple finals1 = (4)
The tuple of final states for M1

Machine M1 = ('ab!', [{'b': 1}, {'a': 2}, {'a': 3}, {'!': 4, 'a': 3}, ...
The deterministic sheep language machine (Jurafsky and Martin, Speech and Natural Language Processing, Fig 2.12)

Function Details

[hide private]

simple_det_recognize(machine, string)

source code

See Jurafsky and Martin, Speech and Natural Language Processing, Fig 2.13

>>> simple_det_recognize(M1,'Baaa!')
False
>>> simple_det_recognize(M1,'baaa!')
True
>>> simple_det_recognize(M1,'baaa')
False

Parameters:

machine (tuple) - a triple of an alphabet, a transition table and a list of final states
string - the string to be accepted or rejected

Returns: boolean

True if the string is accepted by machine

get_transition_value(transitions, symbol)

source code

Having this function wrapper here allows some abstraction in how transition functions are implemented.

Parameters:

transitions (dictionary (Java HashMap)) - transition map from chars to next state for this state

Returns: int or 'und'

set_transition_value(transitions, sym, value)

source code

Having this function wrapper here allows some abstraction in how transition functions are implemented.

Parameters:

transitions (dictionary (Java HashMap)) - transition map from chars to next state for this state
sym - the symbol for which the transition mapping is being defined.

Returns: int or 'und'

det_recognize(machine, string)

source code

Differs from simple_det_recognize in printing explicit error diagnostics for failure. For example, for the case where symbols not in the alphabet occur in string. Instead of raising a KeyError, det_recognize printa an explicit error message and fails.

Also: reports when a state is undefined for input symbol in alphabet before failing, And reports being in a nonfinal state at ethe termination of input before failing.

Parameters:

machine (tuple) - a pair of a transition table and a list of final
string - the string to be accepted or rejected

Returns: boolean

True if the string is accepted by machine

add_sink_state(machine)

source code

Return a new machine just like machine but with an added sink state, k. If new_table is the new machine's TransitionTable, and table is machine's TransitionTable, then for each sym in alphabet, get_transition_value(k, sym) = k. For each sym in alphabet and each state i, if get_transition_value(i, sym) = 'und', get_transition_value(i, sym) = k.

>>> M2=add_sink_state(M1)
>>> det_recognize(M1,'baa!')
True
>>> det_recognize(M2,'baa!')
True
>>> det_recognize(M1,'baab')
State 3 not defined for b
False
>>> det_recognize(M2,'baab')
Ending in non-final state 5
False
>>> det_recognize(M1,'Baa!')
B not in input alphabet
False
>>> det_recognize(M2,'Baa!')
B not in input alphabet
False

Parameters:

machine - the machine to be transformed

Returns: Machine

Variables Details

[hide private]

M1

The deterministic sheep language machine (Jurafsky and Martin, Speech and Natural Language Processing, Fig 2.12)

Type:: Machine

Value:

('ab!', [{'b': 1}, {'a': 2}, {'a': 3}, {'!': 4, 'a': 3}, {}], (4))