[Solved]: What's the definition of a (deterministic) formal language?

Problem Detail: 

Definitions

According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses is deterministic. According to him it means "strictly predictable", which means its only interpretable in a single way. So one input can't map to two outputs.

Confusion

If I'm given any example of a language that humans invented, I can't tell nor elaborate whether it's a formal language or not. Some of these examples are natural languages (English, French, Dutch, etc.), UML, Math, notesheets, programming languages, markup languages, braille.

In my teachers powerpoint presentation, he explained a natural language is not formal because it's dependent on context (Unless I understand the definition of "deterministic" wrong, deterministic is the opposite of context dependency. By context dependency I mean, a sentence or a word can have two different meanings, e.g. You were right. But also Make a right turn at the light Thus a natural language is not deterministic).

But then a few slides later he said a formal language doesn't have to be deterministic, which makes me wonder why he would use context dependency as an argument to explain formal languages in the first place.

Question

What makes a language formal? Perhaps you can elaborate by using the examples given above. And what makes a language deterministic? Is it correct that deterministic is the opposite of context dependency?

N.B. Wikipedia isn't making much sense to me, and I've read that the article about formal languages is quite a mess because people have different opinions on it.

Asked By : user1534664

Answered By : babou

The word formal has many meanings, among which you have:

• being precisely defined mathematically, or at least with very precise rules.

• being devoid of meaning.

In the case of formal languages in Computer Science, it is both: pure representation (syntax) with no meaning.

A formal salute is according to rule, and often devoid of feeling.

Lack of meaning does not mean that no meaning can be attached, but at least that none is being considered at first.

But the use of words and qualifiers must always be considered in context. A formal language, defined mathematically by a context-free grammar, may have no meaning. Then, it is possible to attach meaning to it in formally (mathematically) precise ways. This meaning can be a precise mathematical meaning, and we can then talk of formal semantics. That is how, for example, programming languages are now often defined, very precisely. It also apply to other mathematical languages.

If you consider natural language (say English), it was not created that way, but evolved by users, independently of a formal mathematical model, Furthermore, it does have semantics and exists for only that purpose. So it can on no account be considered formal.

Not only it is not syntactically formal, but its semantics is not formal either, because it is also evolved, and because it does depend on a context that is not precisely definable.

Regarding the word deterministic, it also has several meanings depending on context.

In computer science, a formal language is detrministic if there is a formal (mathematically defined) deterministic device (automaton) that can identify the sentences of the language. Here, the term deterministic means only that for a given sentence to be recognized, this automaton will always work/compute/behave in exactly the same way. A non-deterministic automaton is one that may have one of several well defined behaviors on the same input sentence (independently of any contextual issue). Automata are one way to define formal languages in computer science. Such a language is said to be deterministic if it can be defined by a deterministic automaton, and non-dterministic if it can only be defined by a non-deterministic automaton (I am skipping a lot of important details).

This is clearly not the meaning intended by your teacher, according to what you are saying. For him, something is deterministic when it is context independent, from a semantic point of view. In this sense, natural language is non deterministic (though I would never say it that way). I would rather called that "contextual".

In that sense, "non-deterministic formal automata" are deterministic since their "erratic" behavior (which needs to be explained) is independent of any context.

You can use words for any purpose, if you are careful to define what you mean. However I would never use "deterministic" as the opposite of "context dependent". A better word might be "univocal", or "non-contextual", or "context indpendent".

What really matters is to agree with your teacher on the meaning of words for the purpose of your course. Once you have passed the exam, you will be free to use a different terminology if convenient or required by a new environment, as long as you keep the concepts and possibly use other words to express them.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33842