In the general case, a language is an infinite set, and infinite objects are even difficult to define: they cannot be defined by simply listing the elements. Any finite mechanism for specifying a language is called a grammar.
A formal language is a set of strings in some finite alphabet. Formal languages include artificial languages for human-machine communication—programming languages.
To specify a description of a formal language, it is necessary, firstly, to specify the alphabet, i.e., a set of objects called symbols (or letters), each of which can be reproduced in an unlimited number of copies (like ordinary printed letters or numbers), and, secondly, to define a formal grammar of the language, i.e., list the rules by which symbols are used to construct sequences belonging to the language being defined—regular chains.
The rules of formal grammar can be considered as products (inference rules), that is, elementary operations that, when applied in a certain sequence to the original chain (axiom), generate only correct chains. The very sequence of rules used in the process of generating a certain chain is its conclusion. Language defined in this way is a formal system.
According to the method of specifying correct chains, formal grammars are divided into generative and recognition ones. Generative grammars include the grammars of the language L,
from which it is possible to construct any “correct” chain indicating its structure, and it is impossible to construct a single incorrect chain. A recognition grammar of a language L is a grammar that allows one to determine whether an arbitrarily chosen string is correct and, if it is correct, then to determine its structure. The recognition grammar sets the criterion for an arbitrary string to belong to a given language.
Formal grammars are widely used in linguistics and programming.
knowledge in connection with the study of natural languages and programming languages.
Automatic and linguistic models are built on the basis of the theory of formal grammars, the foundations of which were laid in the works of N. Chomsky. The main objects with which this theory deals are symbols, which are the basic elements of any non-empty set A of any nature, as well as chains constructed from these elements. The set A is also called the alphabet.
We will denote symbols with lowercase letters of the Latin alphabet, and chains – in the form ffghhh, which we will consider oriented from left to right. We will also denote chains with special symbols - capital letters of the Latin alphabet or Greek letters, for example: = ffg, B = abba. Let us introduce into consideration an empty chain that does not contain a single character.
The length of a chain will be the number of characters included in this chain.
The length of the chain is indicated as follows:
| | = | ffg | = 3;
| B | = | abba| = 4;
The concatenation of two chains X and Y is a chain Z that is obtained by directly merging the chain X on the left and the chain Y on the right. For example, if X = ffg, Y = ghh, then the concatenation of X and Y is the chain Z = ffgghh. Let us denote the concatenation operation by the symbol o. Properties of this operation
can be written as follows:
1) property of closure:
o: A* × A* → A*;
2) property of associativity:
(∀X ∈ A*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
where A* denotes the set of all possible chains (infinite, of course), composed of a finite set A of basic elements (symbols) of the dictionary, including the empty chain ; the symbol x denotes the operation of the Cartesian product of two sets; and X, Y, Z are arbitrary chains belonging to A*.
Consider the pair (A*, 0). Taking into account the listed properties of the operation o, this pair is a semigroup with the identity element or a monoid. In algebra, only a set (in this case A*) equipped with a defined associative operation is called a semigroup.
A string may or may not belong to the language L. Any set of strings L ≤ A* (where A* is a monoid) is called a formal language if this set of strings is defined in the alphabet A.
Example 1. Let A be a set of letters of the Russian alphabet. Then the set of strings composed of five letters represents the formal language L1. Another example of a language defined in the same alphabet is the set of L2 five-letter
words of the Russian language that can be found in a spelling dictionary. Ouch-
one can see L2 ⊂ L1, since many strings of the L1 language are not Russian words.
Let B and C be some subsets of the set A*.
The product of sets B and C is the set D of chains, which is
consisting of concatenation of chains of B and C, i.e.
D = ( X o Y | X ∈ B, Y ∈ C).
The product is denoted as follows: D = BC.
Consider the alphabet A. Let us denote the set consisting of by A0. Define
divide the degree of the alphabet as Аn = An-1 A for each n ≥ 1.
It is not difficult to show that the set of all possible chains of the alphabet
Such a set is called an iteration of the alphabet A. A truncated iteration of the alphabet
Favita A is called
If X and Y are chains of the set A*, then the chain X is called a subchain of the chain
buds Y, when there are chains U and V from A* such that
Moreover, if U is an empty chain, then the subchain X is called the head of the chain
ki Y, and if V is an empty chain, then X is called the tail of the chain Y.
The concatenation of two strings X and Y is denoted XY or XY. Consider pairs of chains (P1, Q1), (P2, Q2), ..., (Pn, Qn) from A* x A*. Thue's relations will be the rules according to which any value
a bud X = U Pi V from the set A* will be associated with a chain Y = U Qi V from the same set A* (i = 1, 2, ..., n) and vice versa. These relations lead to the so-called associative calculus.
If the chain Y is obtained from the chain X by a single application of one Thue relation (i.e., replacing the subchain Pi with the subchain Qi), we will say that X and Y are adjacent chains.
The chain Xn is correlated with the chain X0 if there is a sequence of chains
X0, X1, ..., Xn,
such that X i-1 and Xi are adjacent chains.
Example 2. Let A be the set of letters of the Russian alphabet on which
Lim Thue's relationship, which consists in the right to replace any one letter of a word with any other. Then in the sequence of chains FLOUR, MUSE, LUZA, VINE, POSE, TIME, PORT, CAKE, any two adjacent chains are adjacent, and the chains FLOUR and CAKE are correlated in the sense of the given relationships.
The introduction of Thue's relations makes it possible to identify certain classes of languages among many languages, which are used in the construction of automatic linguistic models of various types.
Thue's relations are two-sided if the chain X is adjacent to the chain Y, and vice versa, the chain Y is adjacent to
chain X. More interesting, from the point of view of the theory of formal grammars, are
There are relationships in which direction is introduced.
In this case, they are called Thue semi-relations or products and descriptions.
mean as follows:
(P1 → Q1), (P2 →Q2), ..., (Pn → Qn).
In the case where there is a set of products, we say that the chain Y is incomplete.
is generated directly from the chain X, and is denoted as X ⇒ Y if there exist chains U and V such that
X = U Pi V, Y = U Qi V,
and (Pi → Qi) – products from this set.
It is also said that X begets Y.
If there is a sequence of chains X0, X1, ..., Xn such that for each
before i = 1, 2, ..., n
X i-1 ⇒ X i,
then they say that Xn is generated from X0 (X0 generates Xn), and denote it as X0 ⇒ * Xn. .
Chomskyan grammars correspond to formal combinatorial schemes,
which are Thue semi-systems based on Thue semi-relations
Annotation: This section discusses the basics of the discipline: “formal grammar”. This discipline considers any operations with symbols, and its conclusions are widely used in the analysis of formal and “human” languages, as well as in artificial intelligence. This lecture is the most important and, at the same time, the most difficult lecture to understand in the course. In this regard, the author presents the reader only with her conclusions, omitting the mathematical proofs. To better understand the material, you may need to refer to previous and subsequent lectures.
10.1. Alphabet
A person begins learning any language with the alphabet. IN formal grammar language is defined regardless of its meaning. Moreover, the same language can be formed by several grammars! It’s like at school - the result (which can be read at the end of the textbook) is not as important as its receipt - the solution to the problem recorded in the notebook. Therefore, let us approach the definition of the alphabet also formally.
Definition. An alphabet is a non-empty finite set of elements.
In a “classical” language, the alphabet is a set of letters. In phonetics, a set of speech sounds made by humans. In music, this is a set of notes, etc.
Using the alphabet it is often possible to describe infinite set words The set of all words that can be created using grammar (in other words, generated by grammar) is called a language. Unlike the alphabet, language can be infinite.
Any final sequence alphabet characters called a word, or, more professionally, a chain. Chains consisting of characters (a, b, c) will be the following sequences: a, b, c, aa, ab, bc, ac, bb, abba and others. The existence of an empty chain A is also allowed - a complete absence of symbols. The order of the characters in the chain is also important. So, the chains ab and ba are different chains. Further, uppercase Latin letters will be used as variables and symbols, and lowercase Latin letters will denote chains. For example:
X = SVT Listing 10.1.
a string consisting of the characters S, V and T, and in that order.
Definition. The length of a chain is the number of characters in this chain. It is denoted as |x| . For example: |L| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.
If x and y are strings, then their concatenation will be the string xy. Rearranging the chains during concatenation changes the result (as in group theory). If z = xy is a chain, then x is the head and y is the tail of the chain. If we don't care about the head of the chain, we will denote:
Z = … x Listing 10.2.
and if we don’t care about the tail, we will write:
Z = x ...Listing 10.3.
Definition. The product of two sets of chains is defined as the concatenation of all chains included in these sets. For example, if set A = (a, b), and B = (c,d), then:
AB = (ac, ad, bc, bd) Listing 10.4.
In the product of sets, as in concatenation, the order of the factors is important.
Both when concatenating chains and when multiplying sets of chains, the associative law remains true, written as:
Z = (ab)c = a(bc) = abc Listing 10.5.
D = (AB)C = A(BC) = ABC Listing 10.6.
And finally, we determine the degree of the chain. If x is a non-empty chain, then x 0 = (L), x 1 = x, x 2 = xx, x n = x(x) (n-1). The same is true with the degree of sets.
10.2. Terminal and non-terminal symbols
The concept of terminal and non-terminal symbols is closely related to the concept of substitution (or production) rule. Let's define it.
Definition. A production, or substitution rule, is an ordered pair (U, x), written as:
U::= x Listing 10.7.
where U is a symbol and x is a non-empty finite character string.
Characters that appear only on the right side are called terminal characters. Symbols found on both the left and right sides of the rules are called non-terminal symbols, or syntactic units of language. A bunch of non-terminal symbols denoted as VN, and terminal characters- VT.
Note. This definition of terminal and non-terminal symbols true for KS-grammars and A-grammars (see section 10.4.3).
Definition. A grammar G[Z] is a finite, non-empty set of rules containing non-terminal symbol Z at least once on a set of rules. The Z character is called the start character. Next we all non-terminal symbols we will denote it as<символ>.
[Example 01]
Grammar: "number"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Let's give another definition:
Definition. The chain v directly generates the chain w if:
V=x y and w = xuy Listing 10.8.
Where ::= u is a grammar rule. This is denoted as v => w. We also say that w is directly deducible from v. In this case, the chains x and y can be empty.
Definition. We say that v generates w, or w is reduced to v, if there is a finite chain of outputs u0, u1, …, u[n] (n > 0) such that
V = u0 => u1 => u2 => ... => u[n] = w Listing 10.9.
This sequence is called a pin of length n, and is denoted by v =>+ w. And finally they write:
V =>* w if v => w or v =>+ w Listing 10.10.
10.3. Phrases
Definition. Let G[Z] be a grammar, x a string. Then x is called a sentential form if
Definition. Let G[Z] be a grammar. And let w = xuy be a sentential form. Then u is called a phrase of the sentential form w for non-terminal symbol , If:
Z =>* x y and =>+ u Listing 10.11.
Z =>* x y and => u Listing 10.12.
then the string u is called a simple phrase.
You have to be careful with the term "phrase". The fact that =>+ u (the chain u is deducible from ) does not mean that u is a sentence of the sentential form x y; is also necessary chain deducibility x y from the initial symbol of the grammar Z.
To illustrate the phrase, consider [Example 01] the sentential form<чс>1 . Does this mean that the symbol<чс>is a phrase if there is a rule:<число> ::= <чс>? Of course not, since chaining is not possible:<число><1>- from the initial character:<число>. What are sentences of sentential form?<чс>1 ? Consider the output:
<число> => <чс> => <чс><цифра> => <чс><1>Listing 10.13.
Thus,
<число> =>* <чс>And<чс> =>+ <чс>1 Listing 10.14.
Let's consider a formal grammar, which to some extent resembles a fragment of Russian grammar and specifies a formal language consisting of four Russian sentences. This formal grammar uses elements that act as sentence members or parts of speech:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
These elements are enclosed in angle brackets to distinguish them from the actual vocabulary words that make up the sentences of the language. In our example, the dictionary consists of the following five words, or “characters”: V= (house, oak, obscure, old, (dot)). Grammar has certain rules that contain information about how sentences in a language can be constructed using these symbols. One of these rules is:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
This rule is interpreted as follows: “A sentence may consist of a subject, followed by a predicate, then an object, and a period.” There may well be other rules in the grammar that define sentences of a different structure. However, in this grammar there are no such rules. The rest of the rules are:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® obscures
5. <прилагательное>® old
6. <существительное>® home
7. <существительное>® oak
Let's apply this grammar to generate (or output) a sentence.
According to rule 1, the sentence looks like:
<предложение>1®<subject to e><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><addition> 3 →
3 →<adjective e><существительное> <сказуемое> <прилагательное> <существительное> 4 →Old <существительное> <сказуемое> <adjective e><существительное>
4 →Old <существительное > <сказуемое> old <существительное >
6.7 →Old house <сказуемое> an old oak
4 → The old house is obscured by the old oak tree
Thus, we get a ready-made proposal:
An old house is obscured by an old oak tree.
This conclusion can be visualized as a tree. The output tree shows which rules were applied to the various intermediate elements, but hides the order in which they were applied. Thus, it can be seen that the resulting chain does not depend on the order in which the replacements of intermediate elements were made. They say that the tree is "syntactic structure" offers.
The idea of inference shows other interpretations of rules similar to the rule <подлежащее> ® <прилагательное> <существительное> . Instead of saying " subject This adjective, followed by noun", we can say that subject"gives rise to" (or "is derived from it", or "can be replaced by")<adjective><существительное>.
Using the above grammar, three other sentences can also be derived, namely:
An old oak tree obscures the old house.
The old house obscures the old house.
An old oak obscures an old oak.
These sentences and the sentence derived earlier are all the sentences generated by this grammar.
The set consisting of these four sentences is called a language, which is defined by a given grammar ("generated by it" or "derived in it").
One of the formal systems is the substitution system or Thue semi-system (named after the Norwegian mathematician Axel Thue), defined by the alphabet A and a finite set of substitutions of the form:
where α i,β i are words, possibly empty in A, Þ is a substitution symbol, previously understood by us as “implies”, “deduced”.
The Thue system uses relations of the form:
understood as pairs of substitutions:
α i Þ β i (left);
β i Üα i (right).
In the Thue semi-system, the substitution α i Þβ i is interpreted as the inference rule R i . Using these semi-systems, the American mathematician N. Chomsky in the 50s formed and developed the theory of so-called formal grammars, which are their special case.
Let V be a non-empty set of symbols - an alphabet (or dictionary) and, thus, given the set V * of all finite words in the alphabet V. The formal language L in the alphabet V is an arbitrary subset of V *. So, if V contains letters of the Russian language, punctuation marks, space characters, etc., then V * is a hypothetical set that includes all works of great Russian literature (written and future).
Words, mathematical signs, geometric images, etc. can also be used as symbols.
Languages are specified or determined grammar– a system of rules that generate all chains of a given language, and only them.
Formal grammar – formal system, calculus.
There are recognizing, generating and transforming formal grammars.
recognizing, if for any given string it decides whether that string is correct in the sense of the given grammar.
Formal grammar is called generative, if it can construct any correct chain.
Formal grammar is called transformative if for any correctly constructed chain it constructs its mapping in the form of a correct chain.
Consider the class of generative formal grammars.
The generative formal grammar of G is the quadruple
G=
where T is a finite non-empty set of finite terminal (main) symbols;
N – finite non-empty set of non-terminal (auxiliary) symbols;
P is a finite non-empty set of inference rules (productions);
S is the starting character.
T – terminal dictionary – a set of initial symbols from which the chains generated by the grammar are built;
N – non-terminal dictionary – a set of auxiliary symbols denoting classes of source symbols.
A finite set is a complete dictionary of the grammar G.
The inference rule is a finite non-empty set of binary relations of the form φÞψ, where φ and ψ are chains in the dictionary V, the symbol Þ is “replace with”.
The chain β is directly deducible from the chain α in the grammar G (notation αβ; subscript G is omitted if it is clear which grammar we are talking about) if α=α 1 φα 2 , β=α 1 ψα 2 , (φÞψ).
The chain β is deducible from α if there is a sequence E 0 =α, E 1 ,E 2 ,…,E n =β, such that "i =0,1,...,n-1 E i =>E i +1.
This sequence is called the output β from α, and n is the length of the output.
The deducibility of β from α is denoted by α=> n β (if you need to specify the length of the derivation).
The language L(G) generated by the grammar G is the set of strings in the terminal dictionary T derived from S, where S is the initial symbol denoting the class of linguistic objects for which this grammar is intended. The initial symbol is called the goal of the grammar or its axiom.
Grammars G and G 1 are equivalent if L(G)=L(G 1).
When describing a natural language in terms of the theory of formal grammars, terminal symbols are interpreted as words or morphemes - the smallest meaningful units of language (roots, suffixes, etc.), non-terminal symbols - as names of classes of words and phrases (subject, predicate, predicate group, etc. .P.). A string of characters is usually interpreted as a natural language sentence.
Example 1. Let the grammar be given as follows:
T-(a,b), N-(S,A,B), S-S,
P=(1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb).
Typical conclusions of proposals:
The number of the inference rule used is indicated in parentheses above the arrows. The output ends because there is no rule P with left side equal to ab.
The graph of such a generative grammar is shown in Fig. 125.
Rice. 125. Generative grammar graph
Here a and b are the final vertices (terminal).
Example 2. Let the grammar be given as follows:
T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
You can output the chain<прилежный> <студент> <выполняет> <домашнее задание>.
Obviously, the last chain of inference is final and represents a natural language sentence. Similarly, you can derive the chain<ленивый> <студент> <не выполняет> <домашнее задание>. Note that in this example the nonterminal symbols are syntactic categories.
The output can also be described by the so-called structure tree shown in Fig. 126.
Rice. 126. Structural tree of sentence output
The grammar can also be specified by so-called Wirth syntactic diagrams - as in the Pascal language, which resemble switching circuits in which a serial connection indicates a chain, and a parallel connection indicates variants of the chains - instead of a symbol.
So, formal grammars can be recognizing, generating, transforming. In addition, in the theory of formal grammars, there are four types of languages generated by four types of grammars. Grammars are distinguished by placing successively increasing restrictions on the system of rules R.
The generally accepted classification of grammars and the languages they generate is the Chomsky hierarchy, which contains four types of grammars.
Type 0 grammar is a grammar in which no restrictions are imposed on the rules of inference jÞy, where j and y can be any strings from V. Such a grammar can be implemented by a Turing machine. In this case, the state of the Turing machine corresponds to non-terminal (auxiliary) symbols, and the symbols on the tape correspond to terminal ones. The rules for generating chains are described by a system of commands.
Type grammar 1 is a grammar, all the rules of which have the form aАbÞawb, where wÎТUN, A is a non-terminal symbol. Chains a and b are the context of the rules. They do not change when it is used. Thus, in type 1 grammars, a single terminal symbol A goes into a non-empty string w (A can be replaced by w) only in the context of a and b. Type 1 grammars are called context-sensitive or context-sensitive.
Type 2 grammar is a grammar in which only rules of the form AÞa are allowed, where aÎТUN, i.e. a is a non-empty chain of V. Type 2 grammars are called context-free or context-free. Modern algorithmic languages are described using context-free grammars.
Type grammar 3 – have rules of the form АÞaB, or AÞb, where А,ВОN; a,bÎT.
Here A,B,a,b are single characters (not chains) of the corresponding dictionaries. Languages that are defined by grammars of this type are called automatic or regular.
In this case, a regular expression language (regular language) of the form is used:
Such a language is given by a finite automaton (Kleene's theorem). In most algorithmic languages, expressions are specified using finite state machines or regular expressions.
Let's consider an example of specifying a regular language by a finite automaton:
X=(0,1) – set of input symbols;
Y=(S,A,B,q k ) – set of internal states, q k – final state, S – initial state.
Sometimes several final states are considered and combined into a set F. In this case, F = (q k ).
j: transition function – non-deterministic:
The transition graph of a finite nondeterministic automaton is shown in Fig. 127.
Rice. 127. Transition graph of a finite non-deterministic automaton
The corresponding generative grammar is:
Corresponding regular language L= 
:
0, 010, 01010,...
The theory of formal grammars is used in the construction of compilers. The compiler parses the source program. At the same time, it is determined whether a given chain of characters is a correctly constructed sentence, and, if so, its form is restored. Parsing or syntactic analysis is performed by a special program - a parser (to parse - parse). To solve this problem, special programs have been developed, for example, LEX and YACC.
The UNIX operating system has standard programs LEX and GREP - they are built on the basis of regular language theory.
The LEX program carries out lexical analysis of text - breaking down text in accordance with a specific set of regular expressions.
GREP program - selects a pattern using a regular expression - i.e. conducts a contextual search in one or more files, while building a finite state machine to which symbols from the input symbol stream are fed.
In automatic translation systems from one language to another, the subject, predicate, definition, and complement are identified; then a corresponding proposal is drawn up according to the rules of the required language.
Currently, computers use translators such as Promt, Magic Gooddy, Socrat Personal. In addition, simple dictionaries are used, such as .Context, Socrat Dictionary, MultiLex.
Representation of linguistic knowledge using formal grammars is one of the models of knowledge representation in general, used in such an area as systems with elements of artificial intelligence. It should be noted that knowledge differs from data, for example, in that data are meaningfully interpreted only by the corresponding computer program, and in knowledge the possibility of meaningful interpretation is always present. The software and hardware part of systems that provide an interface with the user in natural or close to natural language is implemented linguistic processor, whose task is the direct and reverse translation of natural language texts into the formal language of the internal representation with which the computer works.
In Japan, some companies have already started selling household “talking” robots that can communicate with the owner.
The linguistic processor has declarative and procedural parts. The first contains a description of dictionaries, the second - an algorithm for the analysis and synthesis of natural language texts.
Logical models for the representation of knowledge are already known to us calculus of propositions and predicates.
The basis for the formalization of semantic (notional) knowledge about a certain subject area are the so-called semantic networks. A semantic network is a directed graph, the vertices of which are associated with specific objects, and the arcs are associated with semantic relationships between them. Vertex labels are referential in nature and represent certain names. The role of names can be, for example, words of natural language. Arc labels denote elements of a set of relations. In addition, frames are used to represent knowledge, which are most often defined as a data structure for representing stereotypical situations.
Gödel's theorems
In mathematical logic it is proven that predicate calculus is consistent - i.e. it is impossible to simultaneously display , and . In addition, by virtue of Gödel's theorem on the completeness of predicate calculus, a generally valid formula is deducible in predicate calculus.
The considered predicate calculus is a first-order predicate calculus. In second-order calculus, quantifiers by predicates are possible, i.e. expressions of the form "P(P(x)), or by functions.
So, the set of all true statements of propositional logic is enumerable and decidable. The set of all true statements of predicate logic is enumerable (due to its completeness), but undecidable (due to the infinity of the subject area).
As another formal theory in mathematical logic, the so-called formal arithmetic proposed by the Italian mathematician Giuseppe Peano (1858-1932) is considered. Peano introduced the symbols and operations O, U, I and was the first to present logic as a mathematical discipline. The first attempt to reduce mathematics to logic was made by the German mathematician and logician Gottlieb Frege (1848-1925). It was he who defined set as the volume of a concept. He wrote: “Arithmetic is a part of logic and should not borrow from either experience or contemplation any foundations of proof.” The famous paradox about the set of all sets is a contradiction in Frege's system identified by Bertrand Russell.
Gödel proved that any formal theory T containing formal arithmetic is incomplete: it contains a closed formula F such that is true, but neither F nor are derivable in T. According to Gödel's famous incompleteness theorem, for any consistent formal theory T containing formal arithmetic, the formula expressing the consistency of T is unprovable in T.
Thus, arithmetic and number theory are non-aximizable theories, and the set of all true statements of arithmetic is uncountable.
Gödel's theorems have important methodological significance. It turns out that for sufficiently rich mathematical theories there are no adequate formalizations. True, any incomplete theory T can be expanded by adding to it as an axiom a formula that is true but not derivable in T; however, the new theory will also be incomplete. In addition, it is impossible to study the metaproperties of a theory using the means of the formal theory itself, i.e. any metatheory T, in order to be able to prove at least consistency, must be richer than T.
Thus, the very approach of constructing mathematics as a certain fixed set of means that could be declared the only legitimate ones and with their help to build metatheories of any theories is called into question. But this is not at all the collapse of the formal approach. The presence of insoluble problems does not mean that a constructive approach is not suitable; if it cannot do something, it is only because no one can do it.
The impossibility of complete formalization of substantively defined theories is not a deficiency of the concept, but an objective fact that cannot be eliminated by any concept.
The impossibility of adequate formalization of a theory means that one must either look for formalizable fragments of it, or build a stronger formal theory, which, however, will again be incomplete, but, perhaps, will contain the entire original theory.
NON-CLASSICAL LOGICICS
INTRODUCTION………… ………………………………….…………….4
Chapter 1. LANGUAGES AND GRAMMAR. SYMBOLS, DEFINITIONS AND CLASSIFICATION………………………………………………………………………………6
1.1. The concept of language grammar. Designations……………………………………………………7
1.2. Classification of grammars according to Chomsky………………………..…………………13
1.3. Techniques for constructing KS- and A-grammars……………………………………………………..16
1.4. Syntactic inference trees in KS-grammars. Performance
A-grammar in the form of a state graph. Ambiguity of grammar……………..19
1.5. Syntactic analysis of A-languages…………………………………………………..23
Exercises……………………………………………………………………………….29
Chapter 2. RECOGNIZERS AND MACHINES.……………………………….….…………32
Chapter 3. AUTOMATINE GRAMMAR AND FINITE MACHINES…………….35
3.1. Automatic grammars and finite automata…………………………………….35
3.2.Equivalence of non-deterministic and deterministic A-grammars...... 36
Exercises………………………………………………………………………………… 41
Chapter 4. EQUIVALENT CONTEXT-FREE TRANSFORMATIONS
AND AUTOMATIC GRAMMARS………………………………………………..….42
4.2. Eliminating dead-end rules from grammars……………………………………46
4.3. Generalized KS-grammars and reduction of grammars to lengthening form…….48
4.4. Elimination of left recursion and left factorization……………………………..…52
Exercises……………………………………………………………………………….53
Chapter 5. PROPERTIES OF AUTOMATIC AND CONTEXT-FREE LANGUAGES…55
5.1. General view of chains of A-languages and KS-languages………………………………………………………..55
5.2. Operations on languages……………………………………………………………….59
5.2.1. Operations on CS languages………………………………………………………59
5.2.2. Operations on A-languages………………………………………………………62
5.2.3. Operations on K-languages………………………………………………………66
5.3. Conclusions for practice…………….…………………………………………………………….67
5.4. Ambiguity of KS-grammars and languages……………………………………………………………71
Exercises………………………………………………………………………………......74
Chapter 6. SYNTACTIC ANALYSIS of CS languages……………………………...……...75
6.1. Methods for analyzing CS languages. Precedence grammars………………….…75
6.2. Wirth's precedence grammars……………………………………………………………...77
Floyd's precedence grammars…….……………………………………………………...79
Precedence functions………………………………………………………81
Exercises………………………………………………………………………………84
Chapter 7. INTRODUCTION TO SEMANTICS……………………………………………………….85
7.1. Polish inverse notation….……………………………………………………...85
7.2. Interpretation of POLIZ……………………………….………………………..….87
7.3. Generating commands for POLIZ………………………………….…………...89
7.4. Zamelson and Bauer’s algorithm for translating expressions into POLIZ………..……….91
7.5. Attribute grammars………………………………………………………………………………97
Exercises………………………………………………………………………………..100
Chapter 8. MAIN PHASES OF COMPILATION……………………………………...……100
CONCLUSION
APPLICATION…………………………………………………………………………………105
SUBJECT INDEX……………………………………………………….…….…115
Introduction
Linguistics- the science of language. Mathematical linguistics- a science that deals with formal methods of constructing and learning languages.
Theory of formal grammars- a section of mathematical linguistics, including methods for describing formal grammars of languages, constructing methods and algorithms for analyzing the belonging of chains to a language, as well as algorithms for translating algorithmic languages into machine language.
The impetus for the creation and improvement of this theory was the development of computer technology and, as a consequence, the need for means of communication between a person and a computer. In all applications, the computer must understand some language in which the user can communicate to it algorithms for solving problems and initial data. Each computer has its own language of machine instructions, represented in binary code and reflecting individual processor operations. At the first stages of the development of computer technology, programmers communicated with computers in this primitive language, but humans are not able to think well in terms of the digital language of the machine. Automation of programming led to the creation first of assembly languages, and then of high-level algorithmic languages, the translation from which into the native machine language was entrusted to the computer itself. Such translation programs are called broadcasters.
Many software developers face the problem of explaining language to a machine. It is human nature to invent new languages. Here we are talking not only about complex compilers for new algorithmic programming languages. Any automated system must understand some input query language. New information technologies involve the involvement of the end user (scientist, designer, technologist, operator) - a specialist in a specific field, and not in the field of computer technology and programming technology, in solving their problems on a computer. For a high-quality solution to this problem, an intelligent interface must exist between the user and the computer: the user must pose problems and obtain the results of their solution in terms of the subject area known to him. That is, it is necessary to develop a wide range of domain-specific languages. A software specialist must know how languages are created and their software support.
To explain language to a machine, we need to have a clear understanding of how it works and how we understand it. When we think about it, we see that we don't know how we understand our mother tongue. The process of this understanding is subconscious and intuitive. But in order to create a translator, it is necessary to have an algorithm for translating text into the actions that this text requires to be performed, and this, in turn, requires language formalization. The problems of language formalization are solved by mathematical linguistics. Natural languages are too complex and it is not yet possible to formalize them completely. Algorithmic languages, on the contrary, are already created with formalization in mind. The theory of formal languages is the most developed branch of mathematical linguistics, which essentially represents a technique for explaining language to a machine. Before looking at the definitions, models and methods of this theory, let's look at some concepts using examples from natural languages.
Language- a set of sentences (phrases) constructed according to certain rules.
Grammar- a set of rules that determine whether a phrase belongs to a language.
Any language must satisfy the properties of decidability and unambiguity.
Language is resolvable, if in a finite time it is possible to determine that a phrase or sentence belongs to the language. The language is unambiguous, if any phrase is understood in a unique way.
The main sections of grammar are syntax and semantics.
Syntax- a set of rules that determine the correct construction of sentences in a language.
Semantics- a set of rules that determine the semantic or semantic correctness of sentences in a language.
A sentence can be syntactically correct and semantically incorrect.
Syntax is usually simplified by the fact that not all phrases in a language need to make sense. It is often difficult to understand the meaning of futurists or the speech of some politicians. In this regard, the example of academician L.V. Shcherba is interesting: “The glokka kuzdra shteko has bald the bokr and is curling the bokrenka.” This is a phrase in Russian, since it can be parsed by the members of the sentence, but its meaning is unclear.
The syntactic analysis of a phrase can be written in the form of a parse tree. The nodes of the tree, such as the subject, predicate, subject group, sentence correspond to syntactic concepts, and the leaves are the words from which the sentence is built. By cutting off some of the leaves and branches in a tree, we get a sentential form (an inferable chain).
<предложение>
The nature of the ambiguity of the phrase can be explained using the example of the same parse tree for the phrase “Mother loves her daughter.”
This phrase is ambiguous because it has two parsing options. Syntactic ambiguity directly entails semantic ambiguity. But you can also offer examples of syntactically unambiguous phrases that may not be understood due to the ambiguous meaning of the words. Let us recall that the algorithmic language must be unambiguous.
A formal language is a mathematical abstraction that arose as a generalization of ordinary linguistic concepts in natural languages. The theory of formal languages studies mainly the syntax of languages and is the foundation of syntactically controlled translation processes, which include translation, assembly and compilation. The foundations of this theory were laid by the American mathematician N. Chomsky in the late 50s and early 60s and continue to develop to this day along with the development of computer technology. Let us dwell on the main elements of this theory.