algorithms, tips or info on dfa correction

[vega_lope]

Hello,

I've implemented a dfa in c, plus the neccesary functions for
insertion, removal and completion of keys within it.

Now I'd like to start studying correction mechanishms (that's how
would I call them).

An example can be the famous "Did you mean: ..." from google, thus, in
my case: given a dfa with a few keys interned on it and a string to
check for, I'd like to be able to catch simple syntax errors or typos
in order to deduce that such a key doesn't exist, but other(s) might
actually be what the user really wanted.

I'd really appreciate if somebody could give me some hint(s),
algorithms' names or resources (books, etc) where I could read
precisely something about this.

Regards,

 

[Walter Roberson]

I've implemented a dfa in c, plus the neccesary functions for
insertion, removal and completion of keys within it.

There are multiple expansions for the abbreviation 'dfa'.
The one I tend to think of is "Deterministic Finite Automata" --
but one does not speak of insertion or removal or completion of keys
for a finite automata. Perhaps you had some other meaning in mind of 'dfa' ?

 

[vega_lope]

There are multiple expansions for the abbreviation 'dfa'.
The one I tend to think of is "Deterministic Finite Automata" --
but one does not speak of insertion or removal or completion of keys
for a finite automata. Perhaps you had some other meaning in mind of 'dfa' ?

My fault. No, I meant a deterministic finite automaton proper, and
yes, I do insert, remove and perform completion of keys on it.

Perhaps my question should be better sent to comp.compilers or some
other ng approaching algorithms or maths.

I'll wait to see if I get some answer here first.

Thanks.

 

[Walter Roberson]

My fault. No, I meant a deterministic finite automaton proper, and
yes, I do insert, remove and perform completion of keys on it.

Sounds a bit unlikely to me. Finite automata do not deal with keys:
they deal with states and transitions, corresponding to the
recognition of regular expressions.

You might, I suppose, use a DFA to validate a regular expression
that happened to have no '*' or '+' operations, and which were thus
"keys" as far as the larger application was concerned, but if that is
what you are doing then it would be better to be more precise --
people's ideas on fuzzy recognition of strings might be different
than their ideas on fuzzy transitions of full regular expressions
complete with '*' and '+' operations.

 

[Antoninus Twink]

My fault. No, I meant a deterministic finite automaton proper, and
yes, I do insert, remove and perform completion of keys on it.

Perhaps my question should be better sent to comp.compilers or some
other ng approaching algorithms or maths.

I'll wait to see if I get some answer here first.

This is a perfectly appropriate place for your question, but as Walter
says, the simple fact is that at the moment the question just doesn't
make sense, so you're unlikely to get a useful answer here or anywhere
else unless you explain more clearly what the problem is.

 

[vega_lope]

This is a perfectly appropriate place for your question, but as Walter
says, the simple fact is that at the moment the question just doesn't
make sense, so you're unlikely to get a useful answer here or anywhere
else unless you explain more clearly what the problem is.

Ok, sorry because it's a bit difficult for me to explain this on a
foreign language, but I've recalled a word that can help here: a trie
(also called try).

I understand a trie (or keyword tree now as well) as a dfa, as soon as
it has a finite set of transitions for every one of it's states.

Opossed to what Walter thinks, a dfa can be used for much more than
just parsing regular expresions; (iirc) automatons as such were
invented in a scientific laboratory, which has nothing to do with
regular expressions, though the human has been using automatons since
it's conception.

"My dfa" deals with keys since I'm able to insert keys on it (words,
keywords),
perform lookups against a given string to see if it exists within it,
remove keys, and perform completion of existing keys as I said
(exactly the same way readline does).

Now that I've finished with the completion algorithm, I'm just looking
forward to see if I can do as google does.

This is, you ask for some key, and a lookup operation returns
unsuccesful,
then, some algorithm gets in the way, doing some sort of trial an
error till it deduces that you made a typo or something, but telling
you either way which key is sintactically "nearest" of the one you did
feed it with.

Thanks.

 

[Walter Roberson]

Opossed to what Walter thinks, a dfa can be used for much more than
just parsing regular expresions; (iirc) automatons as such were
invented in a scientific laboratory, which has nothing to do with
regular expressions, though the human has been using automatons since
it's conception.

The bibliographic notes in Chapter 2 of Hopcroft and Ullman's
"Introduction to Automata Theory, Languages, and Computation" (1979)
say,

The original formal study of finitie state systems (neural nets
similar to that appearing in Exercise 2.2) is by McCulloch and Pitts
[1943]. Kleen [1956] considered regular expressions and modeled
the neural nets of McCulloch and Pitts by finite automata, proving
the equivalence of the two concepts. Similar models were considered
about that time by Huffman [1954], Moore [1956], and Mealy [1955],
the latter two being the sources for the terms "Moore machine"
and "Mealy machine." Nondeterministic finite automata were
introduced by Rabin and Scott [1956], who proved their equivalence
to deterministic automata. [...]


Do you have a citation for the invention of DFA in "a scientific
laboratory"?

 

[Keith Thompson]

On 10 Apr 2008 at 17:21, (e-mail address removed) wrote:

[...]
Ok, sorry because it's a bit difficult for me to explain this on a
foreign language, but I've recalled a word that can help here: a trie
(also called try).

I understand a trie (or keyword tree now as well) as a dfa, as soon as
it has a finite set of transitions for every one of it's states.

Opossed to what Walter thinks, a dfa can be used for much more than
just parsing regular expresions; (iirc) automatons as such were
invented in a scientific laboratory, which has nothing to do with
regular expressions, though the human has been using automatons since
it's conception.

[...]

In any case, as far as I can tell your question isn't about the C
programming language, but about a more general programming issue. At
least initially, any meaningful answers you're likely to get are going
to be independent of the particular implementation language.

I suggest you'll get better information by posting in
comp.programming. If you later run into problems implementing your
solution in C, this would probably be the place to ask.

("Antoninus Twink" told you this is the right place for your question.
He's wrong.)

 

[Walter Roberson]

Now that I've finished with the completion algorithm, I'm just looking
forward to see if I can do as google does.

This is, you ask for some key, and a lookup operation returns
unsuccesful,
then, some algorithm gets in the way, doing some sort of trial an
error till it deduces that you made a typo or something, but telling
you either way which key is sintactically "nearest" of the one you did
feed it with.

http://en.wikipedia.org/wiki/Fuzzy_string_searching

 

[vega_lope]

Something like thishttp://norvig.com/spell-correct.htmlcan help?

Hey, thanks so much Mattia, the link even has c and other languages
translations and it looks like a worth read.

I didn't think of looking for spelling correction even when it is more
or less what I wanted to achive, so I can also now have a look at
ispell's code and see if I can get some word or algorithm there which
helps me going further with this, in the case the link you pasted
doesn't already allow me so.

Thanks so much.