Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | A | B | Bib | C | D | E | Ind

### 6. Some fonctions involving automata

#### 6.1 title

##### 6.1-1 EpsilonToNFA

`> EpsilonToNFA`( A ) | ( function )

A is an automaton with epsilon-transitions. Returns a NFA recognizing the same language.

##### 6.1-2 NFAtoDFA

`> NFAtoDFA`( A ) | ( function )

Given an NFA, computes the equivalent DFA, using the powerset construction, according to the algorithm presented in the report of the AMoRE [MM+95] program. The returned automaton is dense deterministic

##### 6.1-3 SubSetAutomaton

`> SubSetAutomaton`( A ) | ( function )

Is a synonym of `NFAtoDFA`.

##### 6.1-4 AreEquivAut

`> AreEquivAut`( A1, A2 ) | ( function )

Tests if the automata A1 and A2 are equivalent, i.e. recognize the same language. This means that the corresponding minimal automata are isomorphic.

#### 6.2 Minimalization of an automaton

The algorithm used to minimalize a dense deterministic automaton (i.e., to compute a dense minimal automaton recognizing the same language) is based on an algorithm due to Hopcroft (see [AU74]). It is well known (see [HU69]) that it suffices to reduce the automaton given and remove the inaccessible states. Again, the documentation for the computer program AMoRE [MM+95] has been very usefull.

##### 6.2-1 UsefulAutomaton

`> UsefulAutomaton`( A ) | ( function )

Given an automaton A, outputs a dense DFA B whose states are all reachable and such that L(B)= L(A)).

##### 6.2-2 MinimalizeAut

`> MinimalizeAut`( A ) | ( function )

returns the minimal automaton equivalent to A.

##### 6.2-3 MinimalizeDDAutomaton

`> MinimalizeDDAutomaton`( A ) | ( function )

Synonym of MinimalizeAut

##### 6.2-4 MinimalAutomaton

`> MinimalAutomaton`( A ) | ( attribute )

##### 6.2-5 AccessibleDAutomaton

`> AccessibleDAutomaton`( A ) | ( function )

A is a deterministic automaton, not necessarily dense; an equivalent dense deterministic accessible automaton is returned.

##### 6.2-6 AccessibleStates

`> AccessibleStates`( aut, p ) | ( function )

Computes the list of states of the non deterministic automaton aut which are accessible from state p.

##### 6.2-7 AccessibleAutomaton

`> AccessibleAutomaton`( A ) | ( function )

If A is a deterministic automaton, not necessarily dense, an equivalent dense deterministic accessible automaton is returned. (The function AccessibleDAutomaton is called.)

If A is not deterministic with a single initial state, an equivalent accessible automaton is returned.

##### 6.2-8 ProductAutomaton

`> ProductAutomaton`( A1, A2 ) | ( function )

The arguments must be deterministic automata. Returns the product of A1 and A2.

Note: (p,q)->(p-1)m+q is a bijection from 1,ldotsm, ntimes 1,..., m to 1,ldotsm,mn.

##### 6.2-9 IntersectionAutomaton

`> IntersectionAutomaton`( A1, A2 ) | ( function )

The same as ProductAutomaton, but works for all kinds of automata

Top of Book | Previous Chapter | Next Chapter

Goto Chapter: | Top | 1 | 2 | 3 | 4 | 5 | 6 | A | B | Bib | C | D | E | Ind

generated by GAPDoc2HTML