World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

ON PROPER LANGUAGES AND TRANSFORMATIONS OF LEXICALIZED TYPES OF AUTOMATA

    https://doi.org/10.1142/9789814317610_0014Cited by:0 (Source: Crossref)
    Abstract:

    Motivated by the way in which sentences of natural languages are analyzed in linguistics, types of automata are studied that work on extended alphabets which, in addition to the input symbols, also contain certain auxiliary symbols. The latter model the use of (morphological, syntactical, and semantical) categories in the process of analyzing sentences. The automata we consider work on so-called characteristic languages, that is, on languages that include auxiliary symbols. The proper language is obtained from a characteristic language by removing all occurrences of auxiliary symbols. By requiring that the automata are lexicalized, we restrict the lengths of blocks of auxiliary symbols that are admitted. We study the classes of proper languages for deterministic finite-state acceptors, pushdown automata, two-pushdown automata, and freely rewriting restarting automata that are lexicalized. In addition, we use a generalization of the notion of proper language to associate a (binary) transformation with a characteristic language. This leads to the study of transformations of a certain form for the above types of automata.