Discover everything there is to know about the scientific topic Terminal Property with ideXlab!

Noname manuscript No. (will be inserted by the editor) The Syntactic Concept Lattice Another algebraic theory of the context-free languages?

Abstract The syntactic concept lattice is a residuated lattice associated with a given formal language; it arises naturally as a generalisation of the syntac-tic monoid in the analysis of the distributional structure of the language. In this paper we define the syntactic concept lattice and present its basic properties, and its relationship to the universal automaton and the syntac-tic congruence; we consider several different equivalent definitions, as Galois connections, as maximal factorisations and finally using universal algebra to define it as an object that has a certain universal (Terminal) Property in the category of complete idempotent semirings that recognize a given language, applying techniques from automata theory to the theory of context-free gram-mars. We conclude that grammars that are minimal, in a certain weak sense, will always have nonTerminals that correspond to elements of this lattice, and claim that the syntactic concept lattice provides a natural system of categories for representing the denotations of context-free grammars.