Talk:Formal language

Structural linguistics

I once had a book entitled "Structural Linguistics". It appears to me that "formal" here is simply a synonym for "structural", and that "language" is being used to refer to "linguistics". Does structural linguistics merit a mention in this article? Unfree (talk) 22:37, 28 June 2009 (UTC)

Perhaps. Formal language theory is definitely a particular continuation of Structural Linguistics. However, linguistics is the study of natural languages, while formal language theory is mostly applied to artificial ones. Rp (talk) 19:11, 29 June 2009 (UTC)

Feminist grammar

I find nothing in Wikipedia about the alterations to English usage recommended by feminists. Unfree (talk) 22:37, 28 June 2009 (UTC)

You are clearly at the wrong article. There is a hatnote starting with "This article is about a technical term in mathematics and computer science" (my bold). Both of your questions relate to linguistics, so you probably want grammar framework or an article linked from there. Hans Adler 23:40, 28 June 2009 (UTC)

Every set of words

I agree with Hans Adler's edit earlier today. Once one fixes an alphabet, every set of words on that alphabet is a formal language. Moreover, I am not sure what "precise syntactical meaning, programmable for computer interpretation" means. If one starts with an uncountable alphabet, how could the language be programmable for computer interpretation in any sense? — Carl (CBM · talk) 16:09, 30 June 2009 (UTC)

We have a excessive general definition

In the sense defined in this article, one could create a 'formal language' exactly as English, but without empirical semantics. So, altrough even Routlegde Encyclopedia of Philosophy says that "In the most general sense, a formal language is a set of expressions", would be great to include a not-so-general definition in the article. (Rafael, 9 July 2009)

I don't see a problem. If you can give a precise definition of the grammatical sentences of English (actually I am sure you can't), or something that comes pretty close, then you can define a formal language that looks like English. Also, the set of all Wikipedia article source codes as of today midnight GMT is a formal language over the Unicode alphabet.

This is currently a mathematics and computer science article, and for these fields this is a well established standard definition. I am not aware of any variants, other than the occasional assumption that every language is defined by a grammar, which is made either for expository reasons or due to the author's confusion, and is not made in situations where the definition is used in a non-trivial way, i.e. for mathematical existence or non-existence proofs.

If you can find a different precise definition of the term 'formal language', say in linguistics, then it can be added to this article or put into a separate article; or perhaps it will be better known under a different name, and already have an article under that name. Hans Adler 15:01, 9 July 2009 (UTC)

This problem keeps coming up. The article should make it clear why the definition is what it is (namely, that formal language theory is devoted to studying formalisms for defining syntax). Rp (talk) 16:32, 9 July 2009 (UTC)

I agree. Unfortunately it's rare for mathematics texts to discuss the motivations for definitions in detail, so finding a reliable source for such an explanation might prove tricky. Hans Adler 17:21, 9 July 2009 (UTC)

A bit of explanation for this modeling decision is found at the very beginning of Chapter 1 in the Handbook: "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39. Maybe this can serve as a source, I am currently not aware of others. There might be some textbook on Computational Linguistics that elaborates more on this point, but this is a vague guess. Hermel (talk) 09:00, 10 July 2009 (UTC)

Another clue: the book that established most of the framework of formal language theory is called Syntactic structures. Rp (talk) 07:51, 21 July 2009 (UTC)

Merger proposal

It has been proposed to merge the stub Formal language theory into this article. Since it's only a stub, I agree. I guess one could write a big article on the topic. In that case the present article would serve as a simple introduction to just the basic notion, which is also used in fields not closely related to formal language theory. But a temporary merge is OK and probably beneficial. A section on formal language theory in this article might even attract more activity than the separate article. Hans Adler 08:26, 20 August 2009 (UTC)

I agree to merge, especially since it is a stub and reduplicates (only a small part of) the information found in this article. Hermel (talk) 12:15, 20 August 2009 (UTC)

I also agree. What is more, I propose to call the merged article Formal language theory: it may put an end to some of the unsatisfactory discussions we've seen here. Rp (talk) 19:58, 20 August 2009 (UTC)

I am not sure that renaming is a good idea. At the moment it wouldn't really reflect the content of the article, and it might even inspire someone to create a POV fork under the present name. Hans Adler 20:07, 20 August 2009 (UTC)

I'm also not sure about the renaming idea. I support the merge though (since I proposed it). --Robin (talk) 22:00, 20 August 2009 (UTC)

Redundant passage removed

I have just removed the following passage recently added to the article text by Gregbard:

"A formal language can be identified as its set of well formed formulas. If the set of all wffs of a formal language ${\mathcal {L}}$ is identical to the set of all wffs of a formal language ${\mathcal {L'}}$, then ${\mathcal {L}}$ is the same formal language as ${\mathcal {L'}}$; and if not, then it is not the same."

According to the mathematical definition given few lines before that passage, a formal language is nothing else than a set of words, or equivalently, of well formed formulas. Following this definition, the removed passage says that two sets of wffs are the same if the wffs they contan are the same. This is clearly true for any set, so where is the point? Hermel (talk) 16:39, 13 September 2009 (UTC)

I agree. — Carl (CBM · talk) 16:48, 13 September 2009 (UTC)

The reason it is of note is that it contrasts to formal systems in that a formal system cannot be identified by a set of all its theorems. Two formal systems ${\mathcal {S}}$ and ${\mathcal {S'}}$ may have all the same theorems and yet differ in some significant proof-theoretic way ( a formula A may be a syntactic consequence of a formula B in one but not another for instance). The statement itself seems very fundamental to the nature of a formal language, so as to just if its conclusion in the lead paragraph. Pontiff Greg Bard (talk) 22:31, 14 September 2009 (UTC)

The point you seem to want to stress is the following: A formal system is a certain mathematical object, of which a central property are its theorems. But a formal system is more than just a set of theorems, or formulas, and that is why we do *not* consider two formal systems equivalent already if the sets of their theorems are the same. In contrast, a formal language is nothing else than a set of words (in some contexts called wffs or theorems). Thus (of course) we consider two formal languages equivalent already if their wffs coincide. I want to explain my problem with the removed paragraph using a somewhat absurd analogy. The removed paragraph says something like

Two real numbers x,y are considered as being the same if their real parts coincide, i.e. $\Re (x)=\Re (y)$.

Of course, the above sentence no longer holds for complex numbers and thus "seems very fundamental to the nature of a real number". Yet this sentence about the real numbers makes sense only if one already has in mind more complicated objects (complex numbers). It is thus probably more appropriate to explain that difference in the article about formal systems – provided it needs to be explained at all. Hermel (talk) 13:21, 15 September 2009 (UTC)

Image

What exactly is the problem with the clear image explaining these basic relationships? I think if you do not see this as a correct understanding of things I would find that astonishing. These are the basics. Furthermore, I have seen this type of diagram in several different texts on the subject. If there is some clarification to make, I would welcome that, however blank stares or their equivalent will not suffice. Pontiff Greg Bard (talk) 23:52, 12 September 2009 (UTC)

I am quite confused about what the text "Formal languages" at the top is supposed to mean. The formal language consists of the well-formed formulas, so I would expect "formal language" to be in the second square instead of the top. Is it supposed to be a title? If so, I would suggest moving it to the caption. — Carl (CBM · talk) 00:18, 13 September 2009 (UTC)

This is very constructive, I may redo the image soon. It is true that a formal language is identical to its set of wffs. Basically "Formal languages" was intended as a title and also seemed to serve as the title of the "universe" which these squares are slicing up just fine. However if there is confusion, I will address it by removing the title. The diagram is saying that for any formal language there are symbols and strings of symbols ... and among those symbols and strings of symbols some are well formed formulas ... and among those well formed formulas some are theorems. In my mind a diagram like this helps the reader quite a bit. Pontiff Greg Bard (talk) 01:03, 13 September 2009 (UTC)

What exactly is the image conveying? Is it conveying this relationship: The set of theorems is a subset of the set of wffs. The set of wffs is a subset of $\Sigma ^{*}$? --Robin (talk) 02:24, 13 September 2009 (UTC)

That's what I get out of it, now that it has been updated. I don't have any problem with a Venn diagram illustrating the relationships between these things. In the context of the present article, there is an an additional, subtle point. A formal language, on its own, doesn't have "theorems"; one has to introduce some sort of deductive system to get that. So in the context of this article, only the outer two boxes in the diagram are truly relevant. — Carl (CBM · talk) 12:22, 13 September 2009 (UTC)

The content which provided much relevance has been repeatedly removed. I have tried to provide content on the use of formal languages in formal systems, proofs etcetera. It's a big waste of wonderful contributions in an area needing coverage, to which many of the math regulars have been quite hostile. Pontiff Greg Bard (talk) 22:37, 14 September 2009 (UTC)

Gregbard has solved the worst problem, but the image is still not appropriate for this article, at least not in its current position. (Perhaps in a new subsection on logic.) The problem is that the terms well-formed formula and theorem don't occur outside a logic context, and that this logic context is not the overwhelmingly dominating context for the discussion of formal languages at all. If we take ASCII as the alphabet we can consider the set of syntactically correct C programs. These are not called "well-formed formulas" to distinguish them from arbitrary strings of ASCII symbols. And as CBM pointed out, an analogue of "theorems" doesn't even exist in this case. Similarly for linguistics, the original context of formal languages: Given a formal grammar that approximates English, the syntactically correct English sentences are not normally called "well-formed formulas", and again there is no analogue for "theorems". Hans Adler 14:31, 13 September 2009 (UTC)

The image is inappropriate both here and at symbol (formal). CBM and Hans Adler explain it pretty well. The theorems that come from a given deductive system do constitute a formal language, just like grape juice fermentation constitutes a chemical reaction, but we wouldn't expect a large diagram about wine varieties at the top of the general article about chemistry. I'd suggest having a section about complexity classes, in which the theorems of some mathematical theories could be mentioned as examples of recursively enumerable languages. 207.241.229.56 (talk) 23:05, 15 September 2009 (UTC)

I have to strongly disagree with this very silly analogy. While almost all (if not all) the mathematical and computer use of formal language can expressed in terms of the logical uses of formal language, it is not true that all of chemistry consists in variations of grape juice. This content is either appropriate here or we need to create formal language (logic), which I am increasingly seeing as inevitable. Pontiff Greg Bard (talk) 21:09, 17 September 2009 (UTC)

I think it's a bit idiosyncratic to think of formal languages as a topic within mathematical logic, rather than one slightly intersecting it. I don't see a need for a separate logic-specific article about formal languages either, but that's a separate issue. Sure, all the stuff in Hopcroft and Ullman's book can be expressed in terms of mathematical logic, but so can basically everything else in mathematics (that's the whole point of mathematical logic). We still treat mathematical logic as a branch of mathematics, not the other way around. 207.241.229.56 (talk) 03:22, 18 September 2009 (UTC)

proposed expansion

The current state of the article seems pretty skimpy to me, despite the excessive diagram. I think it could be refactored/expanded with an outline something like this:

• Mathematical definition
• Formal grammars
• Chomsky hierarchy and relation between grammars and automata
• complexity classes
• deductive systems and theories
• maybe another topic or two, like infinitary languages

The logic section would allow getting in a mention of wff's and theorems. I might attempt this in my nonexistent free time. Anyone else is of course also welcome to.

207.241.229.56 (talk) 23:40, 15 September 2009 (UTC)

Please be careful not to elaborate on topics that have their own articles. Rp (talk) 00:22, 18 September 2009 (UTC)

Some of the topics that have their own articles shouldn't, and should be reabsorbed here. — Arthur Rubin (talk) 00:25, 18 September 2009 (UTC)

Are you referring to any of the six bullets above? — Carl (CBM · talk) 00:47, 18 September 2009 (UTC)

I was thinking in terms of having a paragraph or so about each of the bulleted topics, with a "main article: ..." link to the separate article about the topic. "Formal language" would become an overview article, since it reaches out into a lot of different areas. 207.241.229.56 (talk) 03:13, 18 September 2009 (UTC)

OMG

Having just read through the talk archive of this article, I see there's been longer-running disagreements than I'd realized. I admire Gregbard's enthusiasm but Hans Adler and CBM really do know what they're talking about. Greg, you might read the Hopcroft and Ullman book cited in the article. It is pretty accessible without requiring knowing a lot of math. It is probably the most reliable source in the subject. It has 9785 citations in Google Scholar [1] while Hunter's Metalogic has 56 citations.[2].

I think the article should be rewritten using the H&U book as the main authority for determining weight, with a few other topics like logical theories sprinkled in (and maybe also something from algebra, like the word problem for finite groups). The outline I gave further up should still more or less work.

I notice that the strings/wffs/theorems diagram is gone from this article now, but it is still in some other articles Theorem, Well-formed formula, Syntax (logic), and Symbol (formal), plus Formal language (logic) which is under deletion discussion. I think it is out of place in at least the wff, syntax, and symbol articles. I also don't understand its emphasis on wffs and theorems. CBM would know better than me, but I thought the king of logical theories was true arithmetic, to which I'd say the concept of theorems doesn't apply in the usual sense. The diagram is misleading regarding theories like this. Anyway I mention that to point out that there may still be problems related to the diagram.

I hope the disputes can be sorted out since I'm sure they are burning a lot of people's energy. I personally had a kind of epiphany when I first studied mathematical logic as an undergraduate. I wanted to apply ideas like models and interpretations to everything in life. I got over it. It wasn't quite as bogus as realizing that the universe is a giant burrito and starting a religion based on that, but maybe the comparison will make sense. From surprising statements like "I also believe that Theory and Theory (mathematical logic) are the same, and yet there are two articles. These splits are the result of politics not academics."[3] (e.g. literary theory is part of that topic in mathematical logic?!) I wonder if Greg also had one of those "Eureka" moments from Hunter's book and is pursuing it wherever it goes. If so, it's a wonderful feeling, but try not to take it too seriously. And I wouldn't be surprised if CBM and Hans experienced it even more intensely than I did, since they became research specialists in logic, while I'm just a computer guy. But their perspective at least now is very realistic.

I'm going to try to sign off and stay away from this topic rather than get sucked into it even more. Good luck everyone. 207.241.229.56 (talk) 07:38, 18 September 2009 (UTC)