automaton.eliminate_state(state=-1)

In the Brzozowski-McCluskey procedure, remove one state.

Preconditions:

  • The labelset is oneset (i.e., the automaton is spontaneous).
  • The weightset is expressionset (i.e., the weights are expressions).
  • The state is indeed a state of the automaton, or it is -1, in which case a heuristics is used to select the next state.

See also:

Examples

In [1]:
import vcsn

The following examples with be using this simple automaton as input.

In [2]:
a0 = vcsn.B.expression('ab*c').standard()
a0
Out[2]:
%3 I0 0 0 I0->0 F4 1 1 0->1 a 3 3 1->3 b 4 4 1->4 c 3->3 b 3->4 c 4->F4

We first need to convert this automaton into a spontaneous automaton labeled with expressions. That's the purpose of automaton.lift.

In [3]:
a1 = a0.lift()
a1
Out[3]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨a⟩ 2 2 1->2 ⟨b⟩ 3 3 1->3 ⟨c⟩ 2->2 ⟨b⟩ 2->3 ⟨c⟩ 3->F3

Explicit state elimination

Let's remove state 2:

In [4]:
a2 = a1.eliminate_state(2)
a2
Out[4]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨a⟩ 3 3 1->3 ⟨c+bb*c⟩ 3->F3

Note that the result is a fresh automaton: the original automaton is not modified:

In [5]:
a1
Out[5]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨a⟩ 2 2 1->2 ⟨b⟩ 3 3 1->3 ⟨c⟩ 2->2 ⟨b⟩ 2->3 ⟨c⟩ 3->F3

Let's eliminate state 1.

In [6]:
a3 = a2.eliminate_state(1)
a3
Out[6]:
%3 I0 0 0 I0->0 F2 2 2 0->2 ⟨a(c+bb*c)⟩ 2->F2

We can also remove the initial and final states.

In [7]:
a4 = a3.eliminate_state(0)
a4
Out[7]:
%3 I1 1 1 I1->1 ⟨a(c+bb*c)⟩ F1 1->F1

Eventually, when all the states have been removed, you get a broken automaton, with no states, but a "lone transition" that bears the answer.

In [8]:
a5 = a4.eliminate_state(1)
a5
Out[8]:
%3 Ipost Fpre Ipost->Fpre ⟨a(c+bb*c)⟩

Rest assured that such automata (no states but with one transition) never occur in the normal course of use of Vcsn.

Using the heuristics

Use -1 (or no argument at all) to leave the choice of the next state to eliminate to Vcsn. This is how automaton.expression works.

In [9]:
a1.eliminate_state()
Out[9]:
%3 I1 1 1 I1->1 ⟨a⟩ F3 2 2 1->2 ⟨b⟩ 3 3 1->3 ⟨c⟩ 2->2 ⟨b⟩ 2->3 ⟨c⟩ 3->F3
In [10]:
a1.eliminate_state().eliminate_state().eliminate_state().eliminate_state()
Out[10]:
%3 Ipost Fpre Ipost->Fpre ⟨ac+abb*c⟩

Interactive Examples

You may use the following widgets to see, step by step, how state elimination works.

In [11]:
from IPython.html import widgets
from IPython.display import display
from IPython.utils import traitlets
from vcsn.ipython import interact_h

def slider_eliminate_state(aut):
    ''' Create the list of automata while applying the eliminate_state algorithm.'''
    count = aut.state_number()
    auts = {}
    auts[0] = aut
    for i in range(count):
        aut = aut.eliminate_state()
        auts[i + 1] = aut
    return auts, count

def update_svg(name, value, new):
    interact_h(lambda: display(auts[new]))

class SliderWidget(widgets.IntSlider):
    def __init__(self, auths, count):
        self.auths = auths
        self.value = 0
        self._widget = widgets.IntSlider(description='Algorithm step(s)', min=0, max=count, step=1, value=0)
        self._widget.on_trait_change(update_svg,'value')

    def show(self):
        display(self._widget)
        interact_h(lambda: display(auts[0]))

# Call on the automaton to show.
auts, count = slider_eliminate_state(a1 ** 2)

slider = SliderWidget(auts, count)
slider.show()
%3 I0 0 0 I0->0 F6 1 1 0->1 ⟨a⟩ 2 2 1->2 ⟨b⟩ 3 3 1->3 ⟨c⟩ 2->2 ⟨b⟩ 2->3 ⟨c⟩ 4 4 3->4 ⟨a⟩ 5 5 4->5 ⟨b⟩ 6 6 4->6 ⟨c⟩ 5->5 ⟨b⟩ 5->6 ⟨c⟩ 6->F6