1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ What is a "UML teacher" and what does she teach? $\endgroup$
    – babou
    Dec 4, 2014 at 20:15
  • $\begingroup$ @babou a UML teacher is a teacher that teaches students UML. $\endgroup$
    – user1534664
    Dec 4, 2014 at 20:25
  • $\begingroup$ Is UML supposed to be Unified Modeling Language? So it is unrelated to University of Massachusetts Lowell? I have not seen this for a while and had forgotten. So I searched the web. I wonder what your question has to do with UML? $\endgroup$
    – babou
    Dec 4, 2014 at 21:27
  • $\begingroup$ @babou yes, UML stands for Unified Modeling Language. As an introductory lesson to UML (= a way to define a domain and its processes using diagrams), my teacher explained some words (abstraction, domain, deterministic, formal etc.) that are useful and often used throughout the course I'm following. $\endgroup$
    – user1534664
    Dec 4, 2014 at 21:40

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What does it mean to be "precisely and mathematically defined"? To me it seems that if a language is formal it implies it's also deterministic, because how can a sentence be precise if it has multiple meanings? Can a formal language be non-deterministic? $\endgroup$
    – user1534664
    Dec 6, 2014 at 1:48
  • $\begingroup$ @user1534664 It is a bit hard to answer you because words only have the meaning you decide to give them, at least in a given context. The first problem is context itself. Language is communication, and communication assume a shared context, which is the main problem when including messages in deep space missions. Absolute meaning of a representation does not exist. Then a language is decomposed (approximately) in syntax that concerns representation (text, sound ...) and semantics that is appropriately connected to syntax, and which concerns meaning. $\endgroup$
    – babou
    Dec 6, 2014 at 14:44
  • $\begingroup$ @user1534664 When you ask whether a formal language can be non-deterministic, the answer depends on the context. In a computer science context, the answer is yes, according to a precise definition of all the words in this context. But it could be that a language is both deterministic and non-deterministic, depending on the kind of language family you consider it in: deterministic in one, but not in the other. The reason is because this qualifier is actually intended for automata, and the answer for a language depends on what kind of automaton you want to consider for recognizing that language. $\endgroup$
    – babou
    Dec 6, 2014 at 14:45
  • $\begingroup$ @user1534664 Coming back to my first comment on context, the issue is hard to deal with regarding natural language. For artificial languages such as programming languages or formalized languages used in mathematics, the way out of that problem is to include the context dependence in the meaning. The way this is done is by defining the meaning as a function that takes a context as argument, and then returns whatever (mathematical) meaning should be associated to the syntactic representation given that context of understanding. It is very hard to be precise. $\endgroup$
    – babou
    Dec 6, 2014 at 14:53
3
$\begingroup$

Formal languages could (potentially) mean different things in different contexts. The Wikipedia page explains one sense, while your teacher might be referring to a different (and more informal) sense. You should probably not worry too much about the formal definition of formal language.

The point your teacher is probably trying to get across is that a human language has an undesirable feature: it doesn't always have an accurate denotation. For example, what do we mean by a "sad song"? This doesn't have an accurate denotation. Compare this to "a string of a's and b's", which does have an accurate denotation. This highlights the vagueness of human language. Another problem is polysemy: the same term can have several different meanings. For example, "formal language" can mean "a set of strings over an alphabet" (the Wikipedia meaning) or the more vague "a language in which each expression has a well-defined and unique meaning", which is closer to your teacher's.

In contrast, formal language defines everything in an unequivocal way. You'll see many examples of formal definitions in class, and hopefully the difference will become clear. But more importantly, you are not a philosopher, and so you shouldn't necessarily be able to explain the difference or to consciously identify which is which. Rather, you should understand that in some contexts we try to banish vagueness as far as we can, and present things in a "formal" and unequivocal way. In other contexts, say writing a newspaper article or a novel, we have different aims, but that kind of writing doesn't fit in a UML class.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Your answer does make sense, and that's as far I got before I asked this question, but I've been given homework to give examples of 5 formal languages and 5 non formal languages. So I suppose he does want me to know the difference. $\endgroup$
    – user1534664
    Dec 4, 2014 at 22:08
  • $\begingroup$ Well, the easiest answer would be to list 5 spoken languages and 5 computer languages, but I don't see how this makes you understand the notion of "formal language" better. I also wonder whether you actually need to understand this notion better. $\endgroup$
    – Yuval Filmus
    Dec 4, 2014 at 22:55
  • $\begingroup$ Yeah, I agree with you. I find it to be quite abstract stuff, so I hope I'll understand it "naturally" sooner or later. It's not worth wasting time. For the meantime I'll just consider the definition of a formal language to be "mathematically precise and created by people so a computer can understand it", and an informal language would be "vague" like you described it. The way I view deterministic is just like a mathematical function f(x), where x is a sentence in a language and can only map to one output. I can't really describe it better than this after reading both your and babou's answer. $\endgroup$
    – user1534664
    Dec 4, 2014 at 23:46
  • $\begingroup$ BTW, he mentioned that I can only choose one spoken and one computer language :P That's why I got a bit confused because it's quite difficult to define whether a language is truly formal or not, especially in cases like UML etc. which turned out to be semi-formal. $\endgroup$
    – user1534664
    Dec 4, 2014 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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