Line 145: | Line 145: | ||
Take note the "definition" has other issues as well, such as the undefined term "sentences". The circularity is just the most glaring issue there. — Carl <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 21:09, 21 May 2008 (UTC) |
Take note the "definition" has other issues as well, such as the undefined term "sentences". The circularity is just the most glaring issue there. — Carl <small>([[User:CBM|CBM]] · [[User talk:CBM|talk]])</small> 21:09, 21 May 2008 (UTC) |
||
::If this formulation does not properly define the term formal language, it still defined these terms which are used elsewhere. The other material should be reinserted (as I said in the edit summary) with regard to this context. [[User:Gregbard|Pontiff Greg Bard]] ([[User talk:Gregbard|talk]]) 21:17, 21 May 2008 (UTC) |
Revision as of 21:17, 21 May 2008
This article is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||
|
I would have liked an exposition of the prefix theorem as well as definitioins of all the terms.Also some words on the grammars.
I would particularly like clarification of this paragraph:
A typical language over that alphabet, containing that string, would be the set of all strings which contain the same number of symbols a and b.
Does this mean that exact string? Or, any string composed of the same number of positions with those positions filled by either a or b? So, would aaaaaa be a word? Would aaa not be a word? Or, would only string comprised of 3 b's and 3 a's be words?
It means the language which consists of words containing the same number of a's and b's. Or, strings comprised of n a's and n b's, for some natural number n, are in that language. —Preceding unsigned comment added by 130.232.111.135 (talk) 09:15, 31 August 2007 (UTC)
Improper Phrases and Words
The term "stilted" is a subjective and derogatory word. It has been removed
Technical attention flag
It would help a lot if this article gave an example of some formal languages. It's also important to explain whether or not natural languages are included in the scientific definition of "formal language".
I was hoping to find some technical references (papers/books) but found none...
I'd Like More References
In many other articles in Wikipedia, there are external links, which are linking to useful websites or pages. I hope there will be some useful links in this item, too.
Where are the practical examples?
Exemple: the power of two macro languages (a very practical exemple) may differ... The C preprocessor is not a "Recursively enumerable" language, the M4 is.
Lead section deterioration
The lead section of this article is starting to deteriorate (at least in terms of aesthetic appearance). Anyone care to chime in before remedial counter-measures are taken? dr.ef.tymac 14:24, 30 January 2007 (UTC)
"Formal language"
While the term "formal language" is very useful, I don't think I've ever encountered its use as a technical term, neither within the vocabulary of formal language theory (which always uses just "language", as far as I'm aware) or outside of that field. So this article may be "guilty" of inventing a new term.
Another big problem with the article as it stood was the lack of distinction between formal languages in general, and the specific field of formal language theory, which studies only certain aspects of languages, and doesn't limit itself to formal languages (!) I have remedied this with an introductory paragraph. I feel the content of the present article would be better moved to a separate "Formal language theory" article. The present article could then be replaced by general discussion of formal languages as they are used in mathematics and other fields. That discussion would of course include languages used in all kinds of branches of mathematics, and many languages used in other fields; it could also include graphical languages, and not-so-very-formal languages; and it would definitely include the description of semantics.Rp 10:33, 25 July 2007 (UTC)
- The bare minimum of a "formal language" is FS (logic). It is a "technical" term in logic although formal system is synonymous. Gregbard 11:40, 25 July 2007 (UTC)
- OK good, I am not so familiar with logic, only with formal language theory. Rp 12:38, 25 July 2007 (UTC)
Rick Norwood's leading example (Aug 2007)
Rick Norwood added a useful example to the start of this article that I feel is very useful but in the form originally published it was also confusing. He defined syntax rules for simple numerical equations, then went on to state that formal languages are defined with formation rules that define the well-formed expressions and transformation rules that define equivalence between them. This is indeed a very common practice but not nearly universal and certainly outside the scope of this article, which at least for now is devoted to the formal language theory perspective on languages, and there is no notion of equivalence between strings in formal language theory since it deals with syntax only.
So I have kept and improved the syntax definition rules of the example, but removed the section on the transformation rules. I do feel it would be important to discuss this matter further and I'm not sure where to do it. Rp 13:04, 22 August 2007 (UTC)
- A formal language is not necessarily defined by a finite set of formation rules. Since a formal language is defined merely as set of strings over some finite alphabet, there are formal languages which are not recursively enumerable, even outside the analytical hierarchy. But every language defined by a finite set of formation rules is recursively enumerable, at least by the Church-Turing Thesis. If you give a rigorous definition of the term "formation rule", one can also give a rigorous proof that this is indeed the case (unless the Church-Turing Thesis is false). Another way to see the difference is by the fact that there are countably many recursively enumerable languages, but uncountably many formal languages. Hermel 22 August 2007 —The preceding signed but undated comment was added at 14:33, August 22, 2007 (UTC).
- I feel the real problem here is that there are (at least) two notions of formal language in mathematics and computing science:
- the informal, widely known, broad notion of 'a language with a formally defined syntax and meaning'
- the formal, much narrower (syntax-only) notion of 'a set of finite sequences of elements from a finite set of symbols', only known to people familiar with formal language theory
- I have attempted to make the distinction clear in the text of this article but it is not yet clear enough. Perhaps the article should be split in two. Rp 12:02, 27 August 2007 (UTC)
- I feel the real problem here is that there are (at least) two notions of formal language in mathematics and computing science:
- I disagree with the current status of the introduction. A formal language in itself has no semantics, it's entirely syntactic: A formal language
- is nothing but a set of strings over a finite alphabet. The only distinction a formal language draws is between strings in L and strings not in L.
- This is the mathematical viewpoint of formal language theory, the theory dedicated to the objects of this article.
- If you carefully read works in CS theory and logic using this term, you will mostly see a proper distinction between the definition of syntax
- (this is the formal language that is worked with), and the definition of the meaning assigned to each string (semantics).
- So, please, refrain from splitting the article; The split goes between syntax and semantics, and a formal language is just about syntax.
- Semantics is not an integral part of a formal language itself, but can be *assigned* to it. In particular, we often assign different
- semantics (usually non-/standard semantics) to one and the same formal language.
- Of course, the most useful classes of languages admit some finite representation,
- although the languages themselves may contain infinitely many strings. Such a representation can be given in
- terms of a finite set of formation rules, e.g. a context free grammar.
- Notwithstanding a formal language being an entirely syntactic notion, usually, when working with a formal language, we assign some semantics
- to its members, just as human readers will assign a meaning to this text (for a machine processing this, this text might be just a member of
- some formal language, without any meaning assigned to it).
- Referring to the notion as set of well-formed formulas restricts the notion of "formal language" to its use in logic. For example,
- a compuational linguist would not say that the members of a language are wffs.Hermel (talk) 21:13, 14 February 2008 (UTC)
- The problem is that we're tryingto cover two different notions in the same article. The term "formal language" is quite broad, but generally applies to language with a formal character or with formal specifications. Such languages have both syntax and semantics (and if they didn't, they wouldn't be languages). However, most of the article is devoted to the notion of language as studied in formal language theory, and this notion is syntax-only, because formal language theory devotes itself to syntax. Perhaps it's better to split the article in two! Rp (talk) 09:35, 15 February 2008 (UTC)
Lambda or epsilon?
169.231.46.33 has been changing quite a few references for the empty string from epsilon (ε) to lambda. I'm almost certain that the convention is and always has been ε, but I'll hold back reverting the changes if someone can prove otherwise.
- charlie liban (talk) 05:47, 23 March 2008 (UTC)
Using the letter lambda to denote the empty word is a tradition originating from German-speaking researchers in the early years of formal language theory: In German, "empty word" is "leeres Wort". This symbol also found widespread use in English papers. Later many English speaking researchers have switched to the usage of "epsilon", which is simply a more sticky symbol for English speakers. Nevertheless, having read a few recent papers in the field, I can confirm that also many researchers still use the "good-old-fashioned" symbol lambda today, see e.g. this recent survey: M. Kutrib: The phenomenon of non-recursive trade-offs, Int. J. Found. Comp. Sci., 2004 [1] Or, see also the following encyclopedia article: [2] Comparable is the use of "Trio" (American school) and "Cone" (French school) to denote the same concept, namely families of formal languages with certain properties. So, IMHO no need to revert the lambda.
- Hermel (talk) 21:21, 1 April 2008 (UTC)
- Thank you for the clarification!
- charlie liban (talk) 20:31, 2 April 2008 (UTC)
Please explain reversion
Gregbard, can you please explain why you reverted my changes? It took me about an hour to write the new version. It is based on my experience with formal languages from the POV of mathematics, formal logic, and computer science, i.e. all relevant POVs. The current lede to which you reverted says some things several times, and it claims some things that were simply not true.
You really managed to make me angry now. --Hans Adler (talk) 20:46, 4 May 2008 (UTC)
You also reverted my changes to the formulas. I made sure that all formulas are shown as text rather than pictures under all personal settings. Please specify whether you reverted that part of my work intentionally or not. --Hans Adler (talk) 20:50, 4 May 2008 (UTC)
Some problems with the old lede:
- A formal language can be entirely defined by the way a set of symbols is organized.
- Woolly language. Show, don't tell!
- This way, it can be defined before it has any meaning, without any reference to any meanings of its expressions and before any interpretations are given to it.
- Way too long to say "syntax only, no semantics".
- Formal languages are tools in the field of mathematical logic and computer science. As such they are designed to express the logic of executable programs.
- Wrong. They are not designed (only) for that purpose. And if they were, this wouldn't follow from their use in mathematical logic. There, and in computer science, they are objects of study more than tools, by the way.
- Like languages in linguistics, formal languages generally have two aspects: syntax and semantics.
- Correct. But the way it is written the reader must think this contradicts the previous paragraph.
- The syntax of a language concerns its patterns, the combination of symbols into sequences without regard to the meaning.
- The syntax is defined by the set of rules that govern how the symbols can be used to construct valid expressions.
- The language (not the syntax) can be (not is) defined by such rules. The word "valid" for well-formed is undefined, unusual and utterly misleading here, because it means something entirely different in logic.
- The semantics is what those expressions mean. This is formalized in various ways, depending on the type of language in question.
- The branch of mathematics and computer science which studies exclusively the theory of language syntax is known as formal language theory. In formal language theory, a language is nothing more than its syntax; questions of semantics are not addressed in this specialty.
- What is "in this specialty" supposed to mean? Very obscure style.
- A formal language can be identified by its well formed formulas (wffs).
- It can be defined as its wffs, not identified by them ("show me your wffs and I tell you who you are"). "wff" is a very specific technical term used only in logic and in none of the other fields where formal languages are much more important. Talking about narrow minded...
- The set of well-formed formula of a particular formal language is determined by a fiat of its creator.
- Unencyclopedic.
- Usually, the determination of what is and is not a well-formed formula is laid down by designating:
- a set of symbols, which are the alphabet of the language and
- a set of formation rules, which determine what sequences of symbols from the alphabet are the well-formed formula of the language.
- An extremely verbose way of saying that formal languages are usually defined in terms of a formal grammar.
Everything that this lede says is also in my version, which also says quite a bit more in less space. Except the reference to Hunter -- which makes no sense because it's completely tangential to the topic. I am reinstating my new version now. Please don't revert without giving detailed reasons. --Hans Adler (talk) 21:10, 4 May 2008 (UTC)
- Yet again, the problem is that the article conflates two closely related notions, namely "formal languages" such as languages studied in mathematical logic (which do have semantics) and "languages as studied in formal language theory" (where semantics is not even mentioned). The article should be split into a "Formal language", which perhaps discusses formally defined languages in general, and a "Language (formal language theory)" which is entirely devoted to finite sets of strings - but most of that material is already covered elsewhere. Rp (talk) 18:30, 18 May 2008 (UTC)
Cirsular definition
This "definition" is completely circular:
- If the class α consists of all of the logical and non-logical signs of a formal language \mathcal{L} and the class ℑ consists of all sentences of \mathcal{L} then a formal language \mathcal{L} can be defined as the ordered pair <α, ℑ>.
I'm going to be traveling and unable to discuss this, so I hope someone else can take care of it. — Carl (CBM · talk) 21:00, 21 May 2008 (UTC)
Take note the "definition" has other issues as well, such as the undefined term "sentences". The circularity is just the most glaring issue there. — Carl (CBM · talk) 21:09, 21 May 2008 (UTC)
- If this formulation does not properly define the term formal language, it still defined these terms which are used elsewhere. The other material should be reinserted (as I said in the edit summary) with regard to this context. Pontiff Greg Bard (talk) 21:17, 21 May 2008 (UTC)