Context-free language
In theoretical computer science is a context-free language (English context - free language, CFL) is a formal language that can be described by a context-free grammar. A context-free grammar allows a defined reading process ( interpretation) of expressions of a formal language. It may be decided, first, whether an expression is equivalent to the rules of grammar, and on the other in the course of analyzing a parse tree can be created. A program that does this is called parser. Parsers are used in particular for the processing of programming languages. Also in computational linguistics trying to describe natural languages by context-free grammars rules.
Context-free languages are referred to as type 2 languages of the Chomsky hierarchy. The class of all context-free languages includes the regular languages ( type-3 languages) and is of the class of context-sensitive languages ( type 1 languages) comprises.
We therefore speak of context-free languages , because the rules of the context-free grammars are always applied independently from the context. This distinguishes them from context-sensitive grammars whose rules also depend on the syntactic context.
Characterization
The class of context-free languages corresponding to the class that is accepted by non-deterministic pushdown automaton languages. The language accepted by deterministic pushdown automaton languages are called deterministic context -free languages and are identical to the class of LR ( k ) languages ( cf. LR ( k ) grammar ).
Examples
If there is an alphabet of symbols and, the following languages are examples of context-free languages:
The language contains the words: ,, etc, so getting as many as s s If you select place and the symbols and corresponds to that of properly nested parentheses: for example, or.
The language contains words, etc., ie, all the words that are mirror-symmetrically in the center. As they read from front and rear give the same word, there are palindromes.
The language is context-sensitive but not context-free.
Context-free languages in the definition of the syntax of programming application, it can be defined, for example, arithmetic expressions, and generally correct bracket structures. Limits of context-free languages are in context-relevant properties, such as type checking in programming languages , which can be represented only by context-sensitive grammars. In practice, one uses context-free parsers with additional functions and data structures.
In computational linguistics are modeled with context-free grammars natural languages. If there is an alphabet of words of a language, for example, one can construct with just a few simple rules noun phrases: By the rules, and are correct and expressions in the grammar.
Properties
The class of context-free languages is closed under
- Union
- Reflection
- Concatenation ( chaining )
- Kleene star
- Application of homomorphisms
- Inverse application of inverse homomorphisms
- Averaging with regular languages
It is not closed under
- Average Counter-example: The languages and context-free. But is not context-free.
- Be complete context-free and context-free languages under complementation: proof by contradiction. Then are also context-free. Because of the seclusion under union and De Morgan follows that and thus is context-free. Contradiction: It has already been shown that the average is not context-free.
The financial statements of association can be proved by constructing a new, again context-free grammar: Be and context-free. New start symbol S and new production. with
Similarly, one can show for two context-free languages, the seclusion under concatenation: Be and context-free. New start symbol S and new production. with
Also, the use of Kleene * corresponds to a new, context-free grammar: Be context-free. New start symbol and new production. with
Every regular language is context-free, since every regular grammar is a context-free grammar. There exist context-sensitive languages that are not context-free. One such example is. Pumping lemma each exist in different variants for regular and context-free languages. For context-free languages they describe necessary but not sufficient properties. Evidence that a formal languages is not context- free, and is usually done on the violation of these necessary properties. Often the studied language is thinned suitable first through the intersection with a regular language. This approach is justified by the above-mentioned financial statements section with regular languages .
A long-standing open problem is the question of whether the set of primitive words is context-free.
Typical decision-making problems
Be, and given context-free languages over the alphabet. Then the following typical problems arise:
- Word problem: Belongs to a word?
- Emptiness problem: Is the empty set?
- Finiteness problem consists of a finite set of words (?)
The above- enumerated problems are decidable ( the word problem by the Cocke - Younger - Kasami ) algorithm for context-free languages. The equivalence problem () is not decidable from and including this stage of the Chomsky hierarchy.
Further properties
- DLIN DCFL CFL GCSL CSL
- REG LIN DLIN CFL
- For each there are languages which can be used as interface of context-free languages are, but not as a cut of context-free languages.
Natural language
In linguistics, context-free grammars are also used to describe the syntax of natural languages . However, it was demonstrated for the example of the Swiss German, the language can not be fully described by such a grammar. But context-free grammars (or equivalent formalisms ) are additional data structures used for languages such as Swiss German Widely used in computational linguistics.