SEMIGROUPS, GROUPS AND GRAMMARINFERENCE PROBLEM

Zbigniew Skolicki

Abstract


In the paper we analyse a problem o f inferring a grammarfrom a given sample o f a langu- age. We try topresent an algebraicformalism capable ofdescribing the issue. We consider two cases: a case o f inferring canonical finite-state grammars, and a case o f inferring generał grammars. In both cases we define a semigroup structure. Finally we look at the possibility o f getting a structure o f a group.


Full Text:

PDF

References


Fu K.S.: Syntactic Pattern Recognition and Applications. New Jersey, Prentice-Hall, Inc. 1982

Aho A.V., Ullman J.D.: The Theory o f Parsing, Translation and Compling. Englewood ClifFs,

N.J., Prentice-Hall, Inc. 1972

Chomsky N.: Syntactic Structures. The Hague, Mouton Publishers 1957

Hopcroft J.E., Ullman J.D.: Formal Languages and Their

Relation to Automata. Reading, MA,

Addison-Wesley 1969

Skolicki Z.: Semigroups and automata. ZN UJ (to be printed)




DOI: https://doi.org/10.7494/csci.2002.4.1.3598

Refbacks

  • There are currently no refbacks.