Linear language

The articles linear language and linear grammar overlap thematically. Help me to better differentiate or merge the articles (→ instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Not me 14:20, Apr 19, 2011 (CEST)

The linear languages ( English, linear languages , LIN) is a technical term from the theoretical computer science . So here they are specifically a class of formal languages and represent a real subset of the type 2 languages of the Chomsky hierarchy . At the same time, they contain the regular languages as a real subset.

The main importance of linear languages is that they represent an example of an easy-to-understand class of formal languages.

definition

A formal language is linear if and only if there is a linear grammar that generates this language. A context-free grammar is called linear grammar if there is at most one non-terminal on the right-hand side of each rule. The abbreviation LIN has established itself in the literature .

Examples

Let it be a grammar with: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$

{\ displaystyle N: = \ {S \}}

{\ displaystyle \ Sigma: = \ {a, b, c, \ ldots, z \}}

{\ displaystyle P: = \ {S \ rightarrow \ epsilon, S \ rightarrow a, S \ rightarrow b, \ ldots, S \ rightarrow z, S \ rightarrow aSa, S \ rightarrow bSb, S \ rightarrow cSc, \ ldots, S \ rightarrow zSz \}}

Apparently with these rules all palindromes are over- produced: in the literature it is often referred to as. ${\ displaystyle \ {a, b, \ ldots, z \}}$ ${\ displaystyle L (G)}$ ${\ displaystyle \ mathbf {pal}}$

There are similar rules for language . ${\ displaystyle \ mathbf {count} = \ {a ^ {n} b ^ {n} | n \ in \ mathbb {N} \}}$

Characterizations

The class of linear languages corresponds to the class of of non-deterministic simply reversing pushdown automata (Engl. One turn NPDAs) accepted languages. A basement machine is simply called the reverse if it no longer writes in the basement in all its calculations after reading it once in the basement. The languages accepted by deterministic simply reversing push-down automata are known as deterministic-linear languages , usually abbreviated as DLIN in the literature .
For all linear languages there are grammars that contain only right and left linear rules. (If both types of rules do not appear, the language so defined is already regular .)

The following applies to the example languages presented here: and ${\ displaystyle \ mathbf {count} \ in \ mathbf {DLIN}}$ ${\ displaystyle \ mathbf {pal} \ in \ mathbf {LIN} \ setminus \ mathbf {DLIN}}$

properties

The class of linear languages is completed under the

It is not completed under

Every regular language is also linear, since every regular grammar is also a linear grammar. There are context-free languages that are not linear. A simple example of this is provided by the language defined above : the language is context-free, but not linear. This can be proven with a special pumping lemma (= pumping lemma ) for linear languages. ${\ displaystyle \ mathbf {pal}}$ ${\ displaystyle L ': = \ {uv | u \ in \ mathbf {pal}, v \ in \ mathbf {pal} \}}$

Advanced properties

DLIN DCFL CFL GCSL CSL ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$
REG DLIN LIN METALIN ULTRALIN CFL ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$ ${\ displaystyle \ subsetneq}$

literature

Ludwig Balke, Karl Heinz Böhling . Introduction to automata theory and the theory of formal languages. B · I · Wissenschaftsverlag, Mannheim et al. 1993, ISBN 3-411-16421-2 , ( Informatik 90 series ).

S. Ginsburg and EH Spanier: Finite-turn pushdown automata . In: SIAM journal on control and optimization 4, 1966, 3, ISSN 0363-0129 , pp. 429-453.

Seymour Ginsburg: Algebraic and Automata-Theoretic Properties of Formal Languages . Elsevier et al., Amsterdam et al. 1975, ISBN 0-7204-2506-9 , ( Fundamental Studies in Computer Science 2).

John E. Hopcroft , Rajeev Motwani, Jeffrey D. Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2nd revised edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , ( i - Computer Science ).

Michael A. Harrison: Introduction to Formal Language Theory. Addison-Wesley Publishing Co., Reading MA et al. 1978, ISBN 0-201-02955-3 , ( Addison-Wesley Series in Computer Science ).