ta-sa.org - Nfa-util.C(best viewed in any resolution with any HTML enabled browser) |
|
Main:
Index
Contact
Links
Studies:
Informatics
Scripts
Material
Projects:
Git repository
Programs:
cdplay
ECMS
lip.C
baseclc.c
nfa-util.C
tm.C
psi_pw_decode
bummskraut
PRelay
Perl:
AnyEvent::XMPP
Net::XMPP2
Net::IRC3
Object::Event
AnyEvent::HTTPD
AnyEvent::DNS
AnyEvent::EditText
Deliantra:
Deliantra
GNU Smalltalk:
Links
Other:
Laughing man logo
ta-sa.org
Index
Contact
Links
Studies:
Informatics
Scripts
Material
Projects:
Git repository
Programs:
cdplay
ECMS
lip.C
baseclc.c
nfa-util.C
tm.C
psi_pw_decode
bummskraut
PRelay
Perl:
AnyEvent::XMPP
Net::XMPP2
Net::IRC3
Object::Event
AnyEvent::HTTPD
AnyEvent::DNS
AnyEvent::EditText
Deliantra:
Deliantra
GNU Smalltalk:
Links
Other:
Laughing man logo
ta-sa.org
no software patents!
Nfa-util.C - last change:
added the rest of the content for the new website,
Sat Apr 5 16:42:15 2008 +0200
nfa-util.C - a NFA (Nondeterministic Finite Automaton) utility program
nfa-util doesn't do much at the moment, it just reads in a definition of an NFA (without epsilon transitions) and calculates a DFA from it via subset construction. It is also maybe not the fastes possible implementation, i just wrote it so i can see if my hand made subset constructions come to the same result as the computer would :-).Input file format
The inputfile is a simple ASCII file. An example would be:charset: abc (e) S a A S a C S abc E A b B B a F C b D D b F E a C E abc E
L := {abc} 'union' ({a,b,c}*{abb}),
Finite state: F)
The first line looks like this (BNF):
character ::= [anything which is not whitespace]
alphabet ::= <character>+
epsilon-character ::= <character>
header ::= 'charset:' <alphabet> '(' <epsilon-character> ')'
The first set of characters is the alphabet of the NFA. The character
in the parens must not be one of the ones from the alphabet and will
stand for the epsilon (word with length of 0) in the NFA definition.
(Note: epsilon transitions aren't supported at the moment, but later
they might)
The following lines might be empty or contain a state transition
definition, which looks like:
state-name ::= <character>+ transition ::= <state-name> <character>+ <state-name>If the state-name starts with an '*' it will be interpreted as an finite state. (one which will let the NFA accept a word).
Note: But currently the finite states are not treated differently and the subset construction will not mark any subset which contains a finite state as special. This might change later.
The first state-name is the "current" state, from which the transition edge will start, the second state-name is the destination of the transition. The characters inbetween are a set of characters which will let the NFA go from the current state to the new state.
Note: The first "current" state from the first state transition definition will be interpreted as start state. In our example (above) it will be the state "S".
Note: There isn't much checking on the input data. But the utility dumps it's data to stdout, so you can look if it got everything alright.
Download:
nfa-util.CExample:
Build it with:
# g++ nfa-util.C -o nfa-util
Run with stdin as input:
# ./nfa-util test.nfa
Example run with stdin as input:
# ./nfa-util
charset: abc (e)
S a A
S a C
S abc E
A b B
B a F
C b D
D b F
E a C
E abc E
charset: 'abc' epsilon: e
A:
A -b-> B,
------------
B:
B -a-> F,
------------
C:
C -b-> D,
------------
D:
D -b-> F,
------------
E:
E -a-> C,E,
E -b-> E,
E -c-> E,
------------
F:
------------
S:
S -a-> A,C,E,
S -b-> E,
S -c-> E,
------------
DFA (from subset construction):
{ S }
{ A C E }
{ E }
{ C E }
{ D E }
{ F E }
{ B D E }
{ F C E }