isuniv

Name

isuniv -- test machine for universality

Synopsis

isuniv fa

isuniv <fa

Description

isuniv tests if fa is universal---that is, complete and all reachable states are also final states. isuniv returns 1 and writes universal on standard output if the input fa is universal; it returns 0 and writes nonuniversal otherwise.

fa must conform to the Grail format for machines.

Examples

% cat dfm6
(START) |- 0
0 a 1
0 b 2
0 -| (FINAL)
1 b 2
1 a 0
2 a 1
2 b 2
1 -| (FINAL)
2 -| (FINAL)

% isuniv dfm6
universal

% cat dfm1
(START) |- 0
0 a 1
1 b 2
2 -| (FINAL)

% isuniv dfm1
nonuniversal

Authors