Formal Languages and Formal Grammars

Formal grammar

A formal grammar, or simply a grammar, in the theory of formal languages — is a way of describing a formal language, that is, of singling out a certain subset from the set of all words over some finite alphabet. A distinction is made between generative and recognizing (or analytical) grammars — the former specify rules that can be used to construct any word of the language, while the latter allow one, given a word, to determine whether or not it belongs to the language.

Terms

• Terminal (terminal symbol) — an object directly present in the words of the language corresponding to the grammar, having a concrete, unchangeable value (a generalization of the notion of a «letter»). In formal languages used on a computer, all or part of the standard ASCII characters are usually taken as terminals — Latin letters, digits, and special characters.
• Nonterminal (nonterminal symbol) — an object denoting some entity of the language (for example: a formula, an arithmetic expression, a command) and not having a concrete symbolic value.

History

The theory of languages examines the principles and features of constructing various languages. Before the beginning of the 20th century only natural (spoken) languages existed. At that time, a language was understood as a means of communication between people. With the development of linguistics it was established that means of communication are not unique to humans. Nowadays a language is understood to be any means of communication.

A language includes the following constituent parts:

• a sign system (a set of admissible sequences of signs);
• a set of meanings of that system;
• a correspondence between sequences of signs and meanings.

The signs of a language can be:

• symbols (letters) of some alphabet (the written form of the language);
• sounds (the spoken form of the language);
• gestures, color, smells, etc.

Note that in information technology all information is represented in the form of strings. Thus, any transformation of data in a computer consists of transforming some strings into others.

In any language one can distinguish correct (admissible) and incorrect constructions. The rules for building correct texts make up the syntax of the language. The description of the correspondence between meanings and texts makes up the semantics of the language.

The semantics of a language depends on the origin and nature of the language, i.e. on the nature of the objects the language describes. The syntax of a language depends less on the nature of the language. Therefore, when studying syntax, a formal approach can be used.

The essence of the formal approach is that a language is regarded as a set of formal objects built according to definite rules. Sequences of symbols serve as the formal objects. When such sequences are constructed, their meaning is not taken into account. The emergence and development of the formal approach is connected with the need to solve problems of the following type:

• machine translation from one natural language into another;
• development of translators (compilers);
• pattern recognition.

Depending on their origin and degree of universality, languages can be divided into the types shown in fig. 12.1

Natural languages arise and develop gradually, together with the development of society, over a long period of time.

Artificial languages are developed specifically for a particular field of application over a relatively short period of time.

Universal languages are used for communication among people in everyday life.

Specialized languages serve as a means of communication for a fairly narrow circle of people when exchanging information in some special field of knowledge. Examples of specialized languages can include various professional jargons (the language of computer users), the language of algebra, the language of the algebra of logic, and so on.

The features of natural languages stem from their origin. The main features that make a formal approach to studying natural languages difficult are listed below.

* Dependence of syntax on semantics (meaning). For example, word endings can depend on whether the objects the words refer to are animate or inanimate. As an example, consider two similar phrases:

"Я увидел пень" ('I saw a stump') (What?).

"Я увидел оленя" ('I saw a deer') (Whom?).

* Semantic and syntactic ambiguity. Semantic ambiguity arises because some words can have different meanings. For example, the phrase "Косой шел с косой" ('The cross-eyed man/the hare walked with a scythe') can have different meanings depending on context. Syntactic ambiguity arises from the insufficient rigor of syntactic rules. For example, the phrase "Бытие определяет сознание" ('Being determines consciousness') can be interpreted in different ways. If we assume that the basic element is being, the original phrase can be replaced by the phrase "Бытие является главным, и оно определяет сознание" ('Being is primary, and it determines consciousness'). But the original phrase can also be interpreted this way: "Бытие определяется сознанием" ('Being is determined by consciousness').

* The possibility of paradoxical sentences arising. Paradoxical sentences are constructed so that they can be classified as neither true nor false. An example of a paradoxical sentence is the phrase: "Данное предложение является ложным" ('This sentence is false').

* Dependence of meaning on the situation.

*Variability of language over time.

*A large number of syntactic rules with numerous exceptions.

12.3. Formal languages and their features.

Most artificial languages use formal rules, i.e. rules not dependent on meaning, when constructing sentences. Such languages are called formal. The syntax of formal languages must ensure the possibility of a formal approach to constructing sentences. Formal languages therefore have the following features

• Independence of syntactic rules from meaning.
• The impossibility of paradoxes arising.
• Rigor of syntactic rules and the absence of exceptions.
• A finite number of syntactic rules.

Formal languages, like natural ones, can change over time. But unlike natural languages, these changes appear not gradually but through the emergence of new versions of the language. In this case, different versions of the same language can be regarded as different languages.

The smallest syntactic unit of a formal language is the symbol. A symbol (letter) - is a simple, indivisible sign. The set of symbols of a language make up the alphabet.

Generative grammars

The words of the language defined by a grammar are all the sequences of terminals derivable (generated) from the start nonterminal by the derivation rules.

To define a grammar, one must specify the alphabets of terminals and nonterminals, the set of derivation rules, and also designate a start symbol among the nonterminals.

Thus, a grammar is defined by the following characteristics:

• — the set (alphabet) of terminal symbols
• N — the set (alphabet) of nonterminal symbols
• P — a set of rules of the form: «left-hand side» «right-hand side», where:
  • «left-hand side» — a nonempty sequence of terminals and nonterminals containing at least one nonterminal
  • «right-hand side» — any sequence of terminals and nonterminals
• S — the start (or initial) symbol of the grammar, from the set of nonterminals.

Derivation

A derivation is a sequence of strings composed of terminals and nonterminals, where the first is the string consisting of a single start nonterminal, and each subsequent string is obtained from the previous one by replacing some substring according to one (any) of the rules. The final string is a string consisting entirely of terminals, and therefore constitutes a word of the language.

The existence of a derivation for a given word is the criterion for its belonging to the language defined by that grammar.

Types of grammars

According to the Chomsky hierarchy, grammars are divided into 4 types, each subsequent one being a more restricted subset of the previous one (but also more tractable to analyze):

• type 0. unrestricted grammars — any rules are possible
• type 1. context-sensitive grammars — the left-hand side may contain a single nonterminal surrounded by «context» (sequences of symbols that appear in the same form on the right-hand side); the nonterminal itself is replaced by a nonempty sequence of symbols on the right-hand side.
• type 2. context-free grammars — the left-hand side consists of a single nonterminal.
• type 3. regular grammars — simpler, equivalent to finite automata.

In addition, the following are distinguished:

• Noncontracting grammars. Every rule of such a grammar has the form , where . The length of the right-hand side of the rule is not less than the length of the left .
• Linear grammars. Every rule of such a grammar has the form , or , that is, the right-hand side of the rule may contain at most one occurrence of a nonterminal .

Application

• Context-free grammars are widely used for defining grammatical structure in grammatical (parse) analysis.
• Regular grammars (in the form of regular expressions) are widely used as patterns for text search, splitting, and substitution, including in lexical analysis.

Example — arithmetic expressions

Let us consider a simple language defining a limited subset of arithmetic formulas consisting of natural numbers, parentheses, and arithmetic operation signs. It is worth noting that here, in every rule, only one nonterminal symbol stands to the left of the arrow . Such grammars are called context-free.

Terminal alphabet:

 = {'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}

Nonterminal alphabet:

  { FORMULA, SIGN, NUMBER, DIGIT }

Rules:

1. FORMULA  FORMULA SIGN FORMULA                (a formula is two formulas joined by a sign)
2. FORMULA  NUMBER                               (a formula is a number)
3. FORMULA  ( FORMULA )                         (a formula is a formula in parentheses)
4. SIGN  + | - | * | /                          (a sign is plus or minus, or multiply, or divide)
5. NUMBER  DIGIT                                 (a number is a digit)
6. NUMBER  NUMBER DIGIT                           (a number is a number and a digit)
7. DIGIT  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (a digit is 0 or 1, or ... 9 )

Start nonterminal:

FORMULA

Derivation:

Let us derive the formula (12+5) using the listed derivation rules. For clarity, the sides of each replacement are shown in pairs, with the part being replaced underlined in each pair.

FORMULA (FORMULA)

(FORMULA) (FORMULA SIGN FORMULA)

(FORMULA SIGN FORMULA) (FORMULA + FORMULA)

(FORMULA + FORMULA) (FORMULA + NUMBER)

(FORMULA + NUMBER) (FORMULA + DIGIT)

(FORMULA + DIGIT) (FORMULA + 5)

(FORMULA + 5) (NUMBER + 5)

(NUMBER + 5) (NUMBER DIGIT + 5)

(NUMBER DIGIT + 5) (DIGIT DIGIT + 5)

(DIGIT DIGIT + 5) (1 DIGIT + 5)

(1 DIGIT + 5) (1 2 + 5)

Analytical grammars

Generative grammars are not the only type of grammar, but they are the most widespread in programming applications. Unlike generative grammars, an analytical (recognizing) grammar defines an algorithm that determines whether a given word belongs to the language. For example, any regular language can be recognized by a grammar defined by a finite automaton, while any context-free grammar can be recognized by a pushdown automaton. If the word belongs to the language, such an automaton builds its derivation explicitly, which makes it possible to analyze the semantics of that word.

Formal Languages

A formal language in mathematical logic, computer science, and linguistics is a set of finite words (strings, chains) over a finite alphabet. The concept of a language is most often used in automata theory, computability theory, and the theory of algorithms. The scientific theory dealing with this object is called formal language theory.

In model theory, a language is built from sets of symbols, functions, and relations together with their arity, as well as a set of variables. Each of these sets may be infinite. Logical statements are formed from the language together with universal logical symbols.

A syntactic subdivision within a formal system.

Defining a Formal Language

A formal language can be defined in various ways, for example:

• By simply enumerating the words belonging to the given language. This method is mainly applicable for defining finite languages and languages of simple structure.
• By words generated by some formal grammar (see the Chomsky hierarchy).
• By words generated by a regular expression.
• By words recognized by some finite automaton.
• By words generated by a BNF construction.

For example, if the alphabet is given as , and the language includes all words over it, then the word belongs to . The empty word (that is, a string of zero length) is allowed and is often denoted as , or .

Some other examples of formal languages:

• the set , where is a nonnegative number, and means that is repeated times;
• the set of syntactically correct programs in a given programming language.

Operations on a Formal Language

Some operations can be used to generate new languages from given ones. Suppose that and are languages defined over some common alphabet.

• Concatenation contains all words satisfying the form , where is a word from , and is a word from .
• Intersection contains all words contained both in and in .
• Union contains all words contained in or in .
• The complement of the language contains all words of the alphabet that are not contained in .
• The right quotient contains all words for which there exists a word in such that was contained in .
• The Kleene closure contains all words that can be written in the form , where is contained in and . Note that this also includes the empty word , since is allowed by definition.
• The reversal contains the reversed words from .
• The shuffle of and contains all words that can be written in the form , where and are such words that the pair is in , and are such words that is in .

Formal Semantics

Formal semantics — a discipline that studies the semantics (interpretations) of formal and natural languages through their formal description in mathematical terms.

A formal language can be defined without any interpretation. This is achieved by specifying a set of symbols (also called an alphabet) and a set of inference rules (also called a formal grammar) that determine which strings of symbols are well-formed formulas. When transformation rules are added and certain sentences are taken as axioms (which together is called a deductive system), a logical system is formed. Interpretation is the assignment of meaning to its symbols and truth values to its sentences.

The truth conditions of the various sentences that may appear in arguments depend on their meaning, so conscientious scholars cannot entirely dispense with some description of the meaning of these sentences. The semantics of logic describes various approaches to understanding and defining those parts of meaning that are of interest. As a rule, what is of interest from a logical point of view is not the sentence itself, but its propositional, idealized form suitable for logical transformations.

Before the emergence of modern logic, in Aristotle's «Organon», namely in the treatise «On Interpretation», the foundations for understanding and the meaning of logic were laid. The introduction of quantifiers was meant to solve the problem of the generality of sets, which could not be solved within the framework of Aristotle's subject-predicate analysis, although in term logic a new interest appears, namely attempts to build a calculus in the spirit of Aristotle's syllogistic, but using the generality properties of quantifiers from modern logic.

The main modern approaches to semantics for formal languages are:

• Model-theoretic semantics, the archetype of Alfred Tarski's truth-theoretic semantics based on his T-schema, is one of the key concepts of model theory. This is one of the most widespread approaches. Its basic idea is that the meaning of the various parts of a statement is given by all possible ways of recursively specifying a group of interpretation functions mapping sentences onto certain predefined mathematical sets. Thus, the interpretation of first-order predicate logic is given by a mapping of terms into a universe, and a mapping of predicates onto the truth values «true» and «false». Model-theoretic semantics underlies the approach in the theory of meaning called conditional truth semantics, which was first proposed by Donald Davidson. Kripke semantics essentially adds some refinements to Tarskian semantics.
• Proof-theoretic semantics links the meaning of statements to the roles they play in reasoning. Gerhard Gentzen, Dag Prawitz (Swed. Dag Prawitz), and Michael Dummett are considered the founders of this approach. It was strongly influenced by the later philosophy of Ludwig Wittgenstein, especially his aphorism «meaning is use».
• Truth-value semantics (also known as substitutional quantification) was proposed by Ruth Barcan Marcus (Eng. Ruth Barcan Marcus) for modal logics in the early 1960s and was later developed in the work of Dunn (Michael Dunn), Belnap (Eng. Nuel Belnap), and Leblanc (Hugues Leblanc) as a standard first-order logic. James Garson (Eng. James Garson) obtained some results in the area of the adequacy of intensional logics equipped with such semantics. The truth conditions of quantified formulas are given exclusively in terms of truth, without using sets (hence the name).
• Game-theoretic semantics was recently revived by Jaakko Hintikka for logics of (finite) partially ordered quantification, which had originally been studied by Leon Henkin.
• Probabilistic semantics — a generalization of truth-value semantics, created by Field (Hartry Field).

Linguists rarely applied formal semantics until Richard Montague showed how English (or any other natural language) could be treated as a formal language. His contribution to linguistic semantics, known as Montague grammar, provides the basis for what linguists call formal semantics.

See also

• Model theory

• JFLAP — a simulator program for automata, Turing machines, and grammars
• Parsing
• Ambiguous grammar
• Smallest grammar problem

• Formal languages and formal grammars
  General concepts	Chomsky hierarchy Alphabet Word
  Type 0	Unrestricted grammar Turing machine Recursively enumerable language Decidable language
  Type 1	Context-sensitive grammar Context-sensitive language Linear bounded automaton
  Type 2	Context-free grammar Ambiguous grammar Context-free language Pushdown automaton (deterministic) Pumping lemma Ogden's lemma
  Type 3	Regular grammar Regular language Regular expression Finite automaton (deterministic, nondeterministic) DFA minimization NFA determinization Myhill—Nerode theorem
  Parsing	LL parser LR parser Recursive descent parsing Cocke—Younger—Kasami algorithm