Контекстсіз грамматика түрлері

Type of formal grammar

In formal language theory, a context free grammar (CFG) is a formal grammar whose production rules
can be applied to a nonterminal symbol regardless of its context. In particular, in a context free grammar, each production rule is of the form

with a single nonterminal symbol, and a string of terminals and/or nonterminals ( can be empty). Regardless of which symbols surround it, the single nonterminal on the left hand side can always be replaced by on the right hand side. This distinguishes it from a context sensitive grammar, which can have production rules in the form with a nonterminal symbol and , , and strings of terminal and/or nonterminal symbols. A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture,

replaces with There can be multiple replacement rules for a given nonterminal symbol. The language generated by a grammar is the set of all strings of terminal symbols that can be derived, by repeated rule applications, from some particular nonterminal symbol ("start symbol"). Nonterminal symbols are used during the derivation process, but do not appear in its final result string. Languages generated by context free grammars are known as context free languages (CFL). Different context free grammars can generate the same context free language. It is important to distinguish the properties of the language (intrinsic properties) from the properties of a particular grammar (extrinsic properties). The language equality question (do two given context free grammars generate the same language?) is undecidable. Context free grammars arise in linguistics where they are used to describe the structure of sentences and words in a natural language, and they were invented by the linguist Noam Chomsky for this purpose. By contrast, in computer science, as the use of recursively defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages. In a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the document type definition. In linguistics, some authors use the term phrase structure grammar to refer to context free grammars, whereby phrase structure grammars are distinct from dependency grammars. In computer science, a popular notation for context free grammars is Backus–Naur form, or BNF.

For any strings , we say u directly yields v, written as , if with and such that and Thus, v is a result of applying the rule to u.

For any strings we say u yields v or v is derived from u if there is a positive integer k and strings such that This relation is denoted , or in some textbooks. If , the relation holds. In other words, and are the reflexive transitive closure (allowing a string to yield itself) and the transitive closure (requiring at least one step) of , respectively.

Another example of a non regular language is It is context free as it can be generated by the following context free grammar:

The formation rules for the terms and formulas of formal logic fit the definition of context free grammar, except that the set of symbols may be infinite and there may be more than one start symbol.

Every context free grammar with no ε production has an equivalent grammar in Chomsky normal form, and a grammar in Greibach normal form. "Equivalent" here means that the two grammars generate the same language. The especially simple form of production rules in Chomsky normal form grammars has both theoretical and practical implications. For instance, given a context free grammar, one can use the Chomsky normal form to construct a polynomial time algorithm that decides whether a given string is in the language represented by that grammar or not (the CYK algorithm).

The following are some decidable problems about context free grammars.

It is decidable whether a given grammar is a regular grammar, as well as whether it is an LL(k) grammar for a given k≥0. If k is not given, the latter problem is undecidable. nor whether it is an LL(k) language for a given k.

Some questions that are undecidable for wider classes of grammars become decidable for context free grammars; e. g. the emptiness problem (whether the grammar generates any terminal strings at all), is undecidable for context sensitive grammars, but decidable for context free grammars. However, many problems are undecidable even for context free grammars; the most prominent ones are handled in the following.

An obvious way to extend the context free grammar formalism is to allow nonterminals to have arguments, the values of which are passed along within the rules. This allows natural language features such as agreement and reference, and programming language analogs such as the correct use and definition of identifiers, to be expressed in a natural way. E. g. we can now easily express that in English sentences, the subject and verb must agree in number. In computer science, examples of this approach include affix grammars, attribute grammars, indexed grammars, and Van Wijngaarden two level grammars. Similar extensions exist in linguistics. An extended context free grammar (or regular right part grammar) is one in which the right hand side of the production rules is allowed to be a regular expression over the grammar's terminals and nonterminals. Extended context free grammars describe exactly the context free languages. Another extension is to allow additional terminal symbols to appear at the left hand side of rules, constraining their application. This produces the formalism of context sensitive grammars.

Chomsky initially hoped to overcome the limitations of context free grammars by adding transformation rules. although his specific examples regarding the inadequacy of context free grammars in terms of their weak generative capacity were later disproved. Gerald Gazdar and Geoffrey Pullum have argued that despite a few non context free constructions in natural language (such as cross serial dependencies in Swiss German), the vast majority of forms in natural language are indeed context free.