2
$\begingroup$
  1. For a formal language $L \subseteq \Sigma^*$ over an alphabet $\Sigma$. From https://proofwiki.org/wiki/Definition:Syntax

    The syntax of a formal language is its structure, and is specified by a formal grammar of the formal language.

    From http://en.wikipedia.org/wiki/Syntax_%28logic%29

    In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning

    • How do you define the "structure" of a formal language, and therefore define the syntax of a formal language? Ideally define them formally or mathematically?

    • The syntax of a formal language should be defined formally, because it pertains to the formal language which is defined formally as a subset of $\Sigma^*$, right?

    • Raphael once said that the syntax of a formal language is the language itself. Is it true?

    • From http://en.wikipedia.org/wiki/Syntax_%28logic%29

      Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formulas of a formal system.

      We shouldn't equate the two concepts: the syntax of a formal language, and a formal grammar of a formal language, should we?

      Note that a formal language can have several formal grammars that all generate the language. When a formal language has multiple different formal grammars that generate it, is the syntax different for different grammar?

      Also a formal language may not have a formal grammar that can generate it, and still syntax should make sense to such a formal language?

  2. For a non-formal language $L'$ over an alphabet $\Sigma$,

    • What are the definitions of its syntax and its semantics, ideally mathematically?

    • When defining its syntax, how do you distinguish what pertains to the formal part of the language, and what is not?

    • Can its semantics be defined as a mapping $L' \to S$ where $S$ is some other set?

    • Maybe, for example, when $L'$ is a programming language?

    • Maybe, for example, when $L'$ is a natural language, such as English?

Thanks and regards!

$\endgroup$
  • $\begingroup$ What in is non-formal language? $\endgroup$ – Dave Clarke Jul 13 '14 at 10:20
  • $\begingroup$ I am a newbie. If you want me to given an answer, a non-formal language is a formal language with additional semantics. $\endgroup$ – Tim Jul 13 '14 at 14:13
  • 2
    $\begingroup$ That's a strange definition – I've never heard anything like that. $\endgroup$ – Dave Clarke Jul 13 '14 at 15:46
5
$\begingroup$

To beging with, the expression "formal language" may refer to formally defined sets of string as considered in the theory of automata and formal languages. I shall write that "Formal Language" with capital first letters. But "formal language" may also refer to some kind of language that is intended for expressing meaning, but is precisely defined mathematically. I shall rather call it formally defined language.

A first remark is that formally defined languages are similar to natural languages (vernacular), in the sense that both are used to convey meaning through representations of that meaning.

This is the fundamental issue. We have to convey meaning, to others, or to ourselves (when we take notes). Meaning can concern all sorts of things, some finite, some infinite, possibly about strange domains of human imaginations, such as real numbers, or the set of all sets. But we can always do that only through representation. The representation may be a linear sequence of symbols. It may also be a spatially organized collection of symbols. It may be drawings, or data structures in a computer, or sound stream, or gestures. It is physical.

To answer the question in a nutshell, and in a very general way: the organisation of the physical representation of discourse is syntax, while semantics is the meaning conveyed, and the way it is derived into, or from, the representation.

A major characteristic of syntax is that syntactic representations are finite: they convey a finite amount of information. This is true of pictures that can de digitized with finite precision to convey what they are supposed to convey, But the best example is one of the most common form of representation: the written text. If one takes all the symbols used for writing as digits in a proper base, any written text may be read an integer number, which is a finite object. This does not prevent the discourse from being about infinite objects, or whatever else, including ghosts, leprechauns, the Zeta function, the turtle that carries the planet on its back and the last Sunday before the Big-Bang. And, this does not forbid having an infinite number of representations, of sentences of the language.

But how is syntax connected to semantics? How do we associate a meaning with physical representation. The most basic way is to associate a specific meaning to specific representations, and learn these associations. This is basically how ideographic writing gets started. But it has limitation: you can define only a finite number of meanings in this way. An important aspect of language is to be able to handle unbounded number of meaning by associating in an organized way the representation of elementary meanings.

So syntax is not just a collection of elementary representations, but also a collection of rules to associate them to make more complex representations. Elementary representations correspond to elementary meanings, and rules associating them indicate how the simpler meanings can be composed to make more complex meanings.

A simple example is the way formally defined languages are specified in mathematics (I am simplifying somewhat, skipping over some technical issues, parsing technology for example). The syntax is defined as a set of string over an alphabet. This set is often defined by a context-free grammar. that provides rules to create strings on the alphabet. The rules also associate strctures to strings: the parse-trees. The definition of semantics associate a value (of whatever domain) to the elements of the alphabet, and associate operations on these values to the rules of the grammar. This define a homomorphism from the set of string in the context-free syntax to the set of values in the semantic domain. (Note that, sometimes, the syntax is directly defined as a set of trees.)

So we have an infinite set (the syntax Formal Language) of finite representations (string or sentences of the formal language) which has a finite definition/description (the Context-Free grammar). The semantics is defined by specifying a domain of values, and both the domain and the values in it may be finite or infinite entities. For example a mathematical text, though finite, can talk about real numbers which are a continuously infinite set of infinite entities (in the sens that most reals do not have a finite description). Furthermore, the mapping is finitely defined, by associating a function with each grammar rule. A rule composes subpart of the text into a larger text, and the associated function composes the meaning of these subparts into a meaning for the larger text.

Not all kinds of Formal Languages may be appropriate for syntax definition. They must provide some structure to the language strings that can be used to define the semantics mapping. Besides context-free languages and grammars, there are many other kinds of Formal Languages and Formal Language Definitions that can provide structure for syntax strings (tree adjoining grammars for example). They are mostly used in computational linguistics for natural language. Other mechanisms, such as attributes or features on grammar symbols, can be added both to specify the strings of the languages or the semantics mapping (but it may be disputed whether they should be considered syntax or semantics).

However, as written earlier, syntax need not be composed of strings of symbols. Other structured representations can be considered, such as graphs, or sound stream. An interesting example is abstract syntax trees that can represent programs of a programming language as tree structures. Some programming systems and development environments actually consider the abstract syntax tree (AST) as the primary representation of programs, and provide tools to create programs represented directly as AST, possibly without ever producing a string representation in some cases. The language Lisp was probably the first to do that. This is also very frequent in proof systems and other symbolic computation systems that manipulate mathematical formulae, which remain represented by tree structures, or even other data types.

This shows that different representation systems, different syntaxes, may be used to represent the same semantic structures. Actually, when these representations can easily be translated into each other, while preserving semantic meaning, they are often considered the same language. In other words, the same language may have multiple syntactic representations, including multiple string syntaxes. But the semantics preserving intertranslatability shows that these different representations are structurally similar. Another obvious example is natural language, that can exist as text or as speech.

Conversely, given a syntax, it is possible to combine it with different semantic interpretations, i.e. different semantic mappings.

$\endgroup$
4
$\begingroup$

For what I know, people from formal languages, logic and natural languages may have slightly different ideas about these notions. That is why (at least in the past) the wikipedia page for formal languages has been terribly messy.

Starting from the bottom: Raphael is right. Syntax is the strings itself. The task of formal languages is to research methods to describe the syntax of languages. This can indeed be grammars, but also machines, logical or algebraic methods. The power of the Chomsky Hierarchy is that several levels of grammar and automata descriptions match (e.g., context-free grammar vs. pushdown automata). That is extremely important because we want to be able to construct a string matching the syntax (writing a program) but also we want to be able to check whether it is correct (parsing and compiling).

Grammars (at least the context-free ones) are important because they have a recursive way of specifying syntax. Using that tool we explicitly or implicitly assign a meaning to strings generated by some parts of the grammar. That is very clear when applied in defining programming languages and natural languages. But then, there is no clear division between syntax and semantics anymore: the derivation tree of the string assigns meaning to parts of the string and their relations. I think that is called "deep structure".

So in that respect, a different grammar implies a different structure, so a different meaning. But that is not completely true. There are grammatical tricks to obtain a variant of a grammar to improve parsing (change "leftmost" into "rightmost") but the overal intended meaning must not change.

(More complicated grammars in my feeling are more like machines: they have a computational aspect, but that aside.)

Semantics is indeed a mapping from strings in the language into some domain. For natural languages that might be the intended "meaning" of a word, but also attributes like male/female, singular/plural (which are not always clear from the isolated syntax, but may be derived from context). For programming languages the semantics may be specified the input/output function of the intended construction, or how the variables are changed. Specifying programming language semantics is a large research area: wikipedia lists already three big major approaches, denotational, operational and axiomatic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.