The files dfa0.in, dfa1.in and dfa2.in contain extended regular expression operators that can only be processed by the dfa program. If nfa and dfa were compiled into executables, named nfa and dfa respectively, then the files nfa1.ex and dfa1.ex would be generated as follows: The automaton for dfa0.in is a *quiver* that has the form triangular grid, with arrows going in the 3 principal directions labelled by a, b and c, such that each a-b-c sequence traverses a loop. The files dfa0.in, dfa1.in and dfa2.in illustrate the first four levels in the approximation series respectively for the languages given as the least fixed point solutions to the following inequalities:ĭfa0.in: S → - a context-sensitive 2-counter languageĭfa1.in: S → - the context-free Dyck Language S -> 1 + a S b Sĭfa2.in: S → - (I'm not sure what this one is) The size of the expression is of the order Q³ in the number of state Q of the dfa, with the following detailed count: Running dfa on it will recover the original automaton back. The files fa8.in, nfa8.ex illustrate the general solution in 4 variables corresponding to the problem of converting a 4-state finite state automaton into a regular expression.
#Finite state automata to regex full
The files fa7.in, nfa7.ex illustrate the full syntax of dfa and nfa, and show their limitations relative to a prospective CFG parsing utility (while also showing the potential for use as the basis of one). Sample inputs are in the files *.in outputs in *.ex listed under the Ref directory.
#Finite state automata to regex manual
Included are descriptions of the various software and (for comparison with rex), the manual section for GNU GREP.
The programs are small: at present, 154 lines (fsc.c), 365 lines (nfa.c), 483 lines (dfa.c), 615 lines (rex.c). These are software demos and sources for regular expressions -> finite automata conversion and regular language accquisition.Īre respectively for RE→NFA conversion, RE→DFA conversion, a "finite state classifier" solution to the regular language acquisition problem, and the rex regular expression text filter.
0 kommentar(er)
