The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] inherently ambiguous languages(1hit)

1-1hit
  • Inherent Ambiguity of Languages Generated by Spine Grammars

    Ikuo KAWAHARADA  Takumi KASAI  

     
    PAPER-Automata and Formal Language Theory

      Vol:
    E88-D No:6
      Page(s):
    1150-1158

    There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, head grammars, and combinatory categorial grammars. It is known that these models of grammars have the same generative power of string languages and fall into the class of mildly context-sensitive grammars. For an automaton, it is known that the class of languages accepted by transfer pushdown automata is exactly the class of linear indexed languages. In this paper, deterministic transfer pushdown automata is introduced. We will show that the language accepted by a deterministic transfer pushdown automaton is generated by an unambiguous spine grammar. Moreover, we will show that there exists an inherently ambiguous language.