[Up] [Previous] [Next] [Index]

4 Noninitial automata

Sections

  1. Definition
  2. Tools

4.1 Definition

  • MealyAutomaton( table[, names[, alphabet]] ) O
  • MealyAutomaton( string ) O
  • MealyAutomaton( autom ) O

    Creates the Mealy automaton (see Short math background) defined by the argument table, string or autom. Format of the argument table is the following: it is a list of states, where each state is a list of positive integers which represent transition function at the given state and a permutation or transformation which represent the output function at this state. Format of the string string is the same as in AutomatonGroup (see AutomatonGroup). The third form of this operation takes a tree homomorphism autom as its argument. It returns noninitial automaton constructed from the sections of autom, whose first state corresponds to autom itself.

    gap> A := MealyAutomaton([[1,2,(1,2)],[3,1,()],[3,3,(1,2)]], ["a","b","c"]);
    <automaton>
    gap> Print(A, "\n");
    a = (a, b)(1,2), b = (c, a), c = (c, c)(1,2)
    gap> B:=MealyAutomaton([[1,2,Transformation([1,1])],[3,1,()],[3,3,(1,2)]],["a","b","c"]);
    <automaton>
    gap> Print(B, "\n");
    a = (a, b)[ 1, 1 ], b = (c, a), c = (c, c)[ 2, 1 ]
    gap> D := MealyAutomaton("a=(a,b)(1,2), b=(b,a)");
    <automaton>
    gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
    < u, v >
    gap> M := MealyAutomaton(u*v*u^-3);
    <automaton>
    gap> Print(M);
    a1 = (a2, a5), a2 = (a3, a4), a3 = (a4, a2)(1,2), a4 = (a4, a4), a5 = (a6, a3)
    (1,2), a6 = (a7, a4), a7 = (a6, a4)(1,2)
    

  • IsMealyAutomaton( A ) C

    A category of non-initial finite Mealy automata with the same input and output alphabet.

  • NumberOfStates( A ) A

    Returns the number of states of the automaton A.

  • SizeOfAlphabet( A ) A

    Returns the number of letters in the alphabet the automaton A acts on.

  • AutomatonList( A ) A

    Returns the list of A acceptible by MealyAutomaton (see MealyAutomaton)

    4.2 Tools

  • IsTrivial( A ) O

    Computes whether the automaton A is equivalent to the trivial automaton.

    gap> A := MealyAutomaton("a=(c,c), b=(a,b), c=(b,a)");
    <automaton>
    gap> IsTrivial(A);
    true
    

  • IsInvertible( A ) P

    Is true if A is invertible and false otherwise.

  • MinimizationOfAutomaton( A ) F

    Returns the automaton obtained from automaton A by minimization.

    gap> B := MealyAutomaton("a=(1,a)(1,2), b=(1,a)(1,2), c=(a,b), d=(a,b)");
    <automaton>
    gap> C := MinimizationOfAutomaton(B);
    <automaton>
    gap> Print(C);
    a = (1, a)(1,2), c = (a, a), 1 = (1, 1)
    

  • MinimizationOfAutomatonTrack( A ) F

    Returns the list [A_new, new_via_old, old_via_new], where A_new is an automaton obtained from automaton A by minimization, new_via_old describes how new states are expressed in terms of the old ones, and old_via_new describes how old states are expressed in terms of the new ones.

    gap> B := MealyAutomaton("a=(1,a)(1,2), b=(1,a)(1,2), c=(a,b), d=(a,b)");
    <automaton>
    gap> B_min := MinimizationOfAutomatonTrack(B);
    [ <automaton>, [ 1, 3, 5 ], [ 1, 1, 2, 2, 3 ] ]
    gap> Print(B_min[1]);
    a = (1, a)(1,2), c = (a, a), 1 = (1, 1)
    

  • IsOfPolynomialGrowth( A ) P

    Determines whether the automaton A has polynomial growth in terms of Sidki Sid00.

    See also IsBounded (IsBounded) and PolynomialDegreeOfGrowth (PolynomialDegreeOfGrowth).

    gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
    <automaton>
    gap> IsOfPolynomialGrowth(B);
    true
    gap> D := MealyAutomaton("a=(a,b)(1,2), b=(b,a)");
    <automaton>
    gap> IsOfPolynomialGrowth(D);
    false
    

  • IsBounded( A ) P

    Determines whether the automaton A is bounded in terms of Sidki Sid00.

    See also IsOfPolynomialGrowth (IsOfPolynomialGrowth) and PolynomialDegreeOfGrowth (PolynomialDegreeOfGrowth).

    gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
    <automaton>
    gap> IsBounded(B);
    true
    gap> C := MealyAutomaton("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
    <automaton>
    gap> IsBounded(C);
    false
    

  • PolynomialDegreeOfGrowth( A ) A

    For an automaton A of polynomial growth in terms of Sidki Sid00 determines its degree of polynomial growth. This degree is 0 if and only if automaton is bounded. If the growth of automaton is exponential returns fail.

    See also IsOfPolynomialGrowth (IsOfPolynomialGrowth) and IsBounded (IsBounded).

    gap> B := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
    <automaton>
    gap> PolynomialDegreeOfGrowth(B);
    0
    gap> C := MealyAutomaton("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
    <automaton>
    gap> PolynomialDegreeOfGrowth(C);
    2
    

  • DualAutomaton( A ) O

    Returns the automaton dual of A.

    gap> A := MealyAutomaton("a=(b,a)(1,2), b=(b,a)");
    <automaton>
    gap> D := DualAutomaton(A);
    <automaton>
    gap> Print(D);
    d1 = (d2, d1)[ 2, 2 ], d2 = (d1, d2)[ 1, 1 ]
    

  • InverseAutomaton( A ) O

    Returns the automaton inverse to A if A is invertible.

    gap> A := MealyAutomaton("a=(b,a)(1,2), b=(b,a)");
    <automaton>
    gap> B := InverseAutomaton(A);
    <automaton>
    gap> Print(B);
    a1 = (a1, a2)(1,2), a2 = (a2, a1)
    

  • IsBireversible( A ) O

    Computes whether or not the automaton A is bireversible, i.e. A, the dual of A and the dual of the inverse of A are invertible. The example below shows that the Bellaterra automaton is bireversible.

    gap> Bellaterra := MealyAutomaton("a=(c,c)(1,2), b=(a,b), c=(b,a)");
    <automaton>
    gap> IsBireversible(Bellaterra);
    true
    

  • DisjointUnion( A, B ) O

    Constructs the disjoint union of automata A and B

    gap> A := MealyAutomaton("a=(a,b)(1,2), b=(a,b)");
    <automaton>
    gap> B := MealyAutomaton("c=(d,c), d=(c,e)(1,2), e=(e,d)");
    <automaton>
    gap> Print(DisjointUnion(A, B));
    a1 = (a1, a2)(1,2), a2 = (a1, a2), a3 = (a4, a3), a4 = (a3, a5)
    (1,2), a5 = (a5, a4)
    

  • A * B

    Constructs the product of 2 noninitial automata A and B.

    gap> A := MealyAutomaton("a=(a,b)(1,2), b=(a,b)");        
    <automaton>
    gap> B := MealyAutomaton("c=(d,c), d=(c,e)(1,2), e=(e,d)");
    <automaton>
    gap> Print(A*B);                                  
    a1 = (a1, a5)(1,2), a2 = (a3, a4), a3 = (a2, a6)
    (1,2), a4 = (a2, a4), a5 = (a1, a6)(1,2), a6 = (a3, a5)
    

  • SubautomatonWithStates( A, states ) O

    Returns the minimal subautomaton of the automaton A containing states states.

    gap> A := MealyAutomaton("a=(e,d)(1,2),b=(c,c),c=(b,c)(1,2),d=(a,e)(1,2),e=(e,d)");
    <automaton>
    gap> Print(SubautomatonWithStates(A, [1, 4]));
    a = (e, d)(1,2), d = (a, e)(1,2), e = (e, d)
    

  • AutomatonNucleus( A ) O

    Returns the nucleus of the automaton A, i.e. the minimal subautomaton containing all cycles in A.

    gap> A := MealyAutomaton("a=(b,c)(1,2),b=(d,d),c=(d,b)(1,2),d=(d,b)(1,2),e=(a,d)");
    <automaton>
    gap> Print(AutomatonNucleus(A));
    b = (d, d), d = (d, b)(1,2)
    

  • AreEquivalentAutomata( A, B ) O

    Returns true if for every state s of the automaton A there is a state of the automaton B equivalent to s and vice versa.

    gap> A := MealyAutomaton("a=(b,a)(1,2), b=(a,c), c=(b,c)(1,2)");
    <automaton>
    gap> B := MealyAutomaton("b=(a,c), c=(b,c)(1,2), a=(b,a)(1,2), d=(b,c)(1,2)");
    <automaton>
    gap> AreEquivalentAutomata(A, B);
    true
    

    [Up] [Previous] [Next] [Index]

    automgrp manual
    September 2008