Talk:Formal grammar

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Foundations, logic, and set theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.
Archive
Archives
/Archive 1


Contents

[edit] Terminology clarification requests

Please feel free to list any potentially bothersome/burdensome/opaque terminology clarification requests here as the article stands, in order that editors not over-clarify the terms. :-)

Current candidates (see archive 1) are:

  • "recognize"

-- QTJ 06:02, 6 November 2006 (UTC)

Also -- analytic grammars are not covered enough per archive 1. Some literature refers to them as "recognitional" models, but that might be covered in "recognize". -- QTJ 06:06, 6 November 2006 (UTC)

In formal language theory, there is no such thing as analytic grammar. (Formalisms to analyze languiage are known as automata.) I have renamed this page to make it 100% clear that it is about the notion of grammar known in formal language theory. Rp (talk) 17:51, 28 December 2007 (UTC)

[edit] context-free grammar

"A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol."

Is this correct? It seems different from the definition in Context-free_grammar. Took 10:22, 2 June 2007 (UTC)

No, it's the same definition. (I'm rather confused by your question, actually — it's not that these are two different definitions that can be proved equivalent, but rather that they're actually the same definition, albeit worded differently. Am I missing something?) —RuakhTALK 16:37, 2 June 2007 (UTC)
The problem is that the definition given in the context-free_grammar article was simply wrong (I have never seen it before, and I suspect it produces a formalism more powerful than context-free grammars.) I have taken the liberty to rewrite it there. Rp 14:58, 24 July 2007 (UTC)
That's really funny. The definition was right when Took wrote his/her comment, then the definition was changed to be wrong, and you're only now seeing his/her comment, which prompted you to take a look and fix the definition. That works really well. :-) —RuakhTALK 15:55, 24 July 2007 (UTC)
I just realize that I misunderstood some word in the above definition. So everything is fine, and glad to see that my comment (unintentionally) helps correct an error :) Took 12:37, 6 August 2007 (UTC)

[edit] Definition of "language"

Does the language generated by a grammar consist only of the results of applications of finitely many production rules, or is there a notion of convergence to deal with? - Brad 65.93.148.11 05:29, 19 August 2007 (UTC)

The language generated consists of words obtainable by a finite number of production rule applications. There is no natural notion of convergence that would allow one to consider infinite number of production rule applications in the context of formal grammars. — Carl (CBM · talk) 15:35, 19 August 2007 (UTC)

[edit] Regular Grammar typo

Just changed the left hand side of rule 6 in the regular grammar example from S to B. With S, the grammar can derive the empty string (which it shouldn't), and every non-empty derived string would contain at least 2 b's (so, e.g., ab could not be derived). So it looks very much like a typo where the S should simply be changed to B.

However, the parenthesis to the right of rule 6 is now inconsistent (because it talks about S, and the rule does not contain S any more). I'm not sure how to resolve that, so I left it unchanged. Anybody who knows exactly how to fix that?

ErikErnst 16:13, 25 September 2007 (UTC)

After a bit more research there seems to be no evidence supporting the statement made in the parentheses to the right of rule 6, so I deleted it.

ErikErnst 16:43, 25 September 2007 (UTC)

[edit] S and alphabet

From the current example: This process is repeated until we only have symbols from the alphabet (i.e., a and b).

S itself must consist of elements of the given alphabet only, right? As we said the alphabet consists of a and b only, the process of transforming S (with which we start in the example) is already finished when we start. --Abdull 11:52, 4 December 2007 (UTC)

In this example S is just a symbol, but not a symbol from the alphabet. It's a symbol that is used to recursively generate strings. The actual strings that are generated are the ones that don't contain S; the ones that do contain S aren't done yet. — Carl (CBM · talk) 14:08, 4 December 2007 (UTC)

[edit] Renaming

This page is useful, but very messy. The main reason, I feel, of its messiness was the continuous attempt to appease both computer scientists and linguists; I have taken the liberty to take what I I felt was the most urgent step to rectify this, namely, renaming it to use well-established terminology. The old name (formal grammar) isn't used by anyone I know. Rp (talk)

I have performed this deletion and move, as requested. I don't do this often, so if there's something that I should have done, or should have done differently, I'd appreciate knowing about it. Accounting4Taste:talk 16:37, 30 April 2008 (UTC)
No, you undid the move I made. Can I please redo it?? Rp (talk) 16:16, 2 June 2008 (UTC)