context-free

(redirected from Context-free language)
Also found in: Wikipedia.

context-free

Said of a grammar where the syntax of each constituent is independent of the symbols occuring before and after it in a sentence. Parsers for such grammars are simpler than those for context-dependent grammars because the parser need only know the current symbol.
References in periodicals archive ?
Maslov (1973); Oshiba (1972) proved that the cyclic closure of a context-free language is context-free.
And the language L(G), generated by the IFCFG G, is said to be an intuitionistic fuzzy context-free language (IFCFL).
In other words, the general predicate can be taken to be 'is a property which it does not possess', and this contains a pronoun, which is a contextual item with no direct representation in a context-free language. This pronominal predicate is functional, in other words, and the nearest one can get to any concept it expresses, in a language without pronouns, is:
This is a prototypical case of context-sensitive but not context-free language.
Unexpectedly, this question turns out to be intimately related to the complexity of deterministic context-free language (DCFL) recognition.
Interconvertibility of a class of set constraints and context-free language reachability.
It was attractive, says Pullum, because "a context-free language can always be handled fairly efficiently.
The branching of the step is defined to be the number of choices [4, 5].Most of the context-free languages differ in the amount of the resource (in this case, nondeterminism) that they require [6, 7].
After a quick overview of necessary prerequisites such as set and graph theory and the study of relations and general logic, the author follows a path that narrows its themes from chapter to chapter: from regular to context-free languages and their models, to Turing machines and specific computation issues, including computability and decidability and general and context-sensitive grammars.
The families of recursively enumerable and context-free languages are denoted by RE and CF respectively.
Topics covered in this volume include basic theory of computation, finite automata, properties of regular languages, context-free languages, Turing machines, limits of algorithmic computation and computational complexity.
Again, the technical part is followed by a theoretical discussion in which PDA are proved to be stronger than finite automata, the computational limits of the model are discussed, and some closure properties of the family of languages accepted by this model (context-free languages) are proved.

Full browser ?