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

Keyword Search Result

[Keyword] linear language(4hit)

1-4hit
  • On the Generative Power of Cancel Minimal Linear Grammars with Single Nonterminal Symbol except the Start Symbol

    Kaoru FUJIOKA  Hirofumi KATSUNO  

     
    PAPER-Fundamentals of Information Systems

      Vol:
    E94-D No:10
      Page(s):
    1945-1954

    This paper concerns cancel minimal linear grammars ([5]) that was introduced to generalize Geffert normal forms for phrase structure grammars. We consider the generative power of restricted cancel minimal linear grammars: the grammars have only one nonterminal symbol C except the start symbol S, and their productions consist of context-free type productions, the left-hand side of which is S and the right-hand side contains at most one occurrence of S, and a unique cancellation production Cm ε that replaces the string Cm by the empty string ε. We show that, for any given positive integer m, the class of languages generated by cancel minimal linear grammars with Cm ε, is properly included in the class of linear languages. Conversely, we show that for any linear language L, there exists some positive integer m such that a cancel minimal linear grammar with Cm ε generates L. We also show how the generative power of cancel minimal linear grammars with a unique cancellation production Cm ε vary according to changes of m and restrictions imposed on occurrences of terminal symbols in the right-hand side of productions.

  • On the Generative Powers of Some Extensions of Minimal Linear Grammars

    Kaoru ONODERA  

     
    PAPER-Automata and Formal Language Theory

      Vol:
    E90-D No:6
      Page(s):
    895-904

    This paper concerns the Geffert normal forms for phrase structure grammars. We first generalize them to have a new formulation of minimal linear grammars with cancellation productions, called "cancel minimal linear grammars". Then the generative powers of some classes of those grammars are investigated. It is shown that the class of languages generated by grammars with a unique {AB}-cancellation production properly includes the class of linear languages, while it is included in the class of context-free languages. Furthermore, the corresponding class of languages generated by grammars with a unique {AA}-cancellation production is shown to be a proper subclass of linear languages.

  • Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages

    Sadaki HIROSE  Satoshi OKAWA  

     
    LETTER-Automata,Languages and Theory of Computing

      Vol:
    E79-D No:2
      Page(s):
    161-164

    In this paper, we give a direct proof of the result of Latteux and Turakainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reductions (which reduce pairs of parentheses to the empty word).

  • A Note on a Completely Linearly Nested Context-Free Grammar and Its Generalization

    Tetsuo MORITA  

     
    LETTER-Algorithms, Data Structures and Computational Complexity

      Vol:
    E77-A No:12
      Page(s):
    2106-2108

    We introduce a generalized cln grammar (gclng), a generalization of a completely linearly nested context-free grammar (clncfg), of which variables are partitioned linearly and each rule satisfies similar conditions as those of clncfg related to its partition. We show that the class of languages generated by gclng's coincides with the class of quasi-rational languages, and consider the inclusion relations between languages generated by gclng's and those generated by clncfg's.