Template talk:Formal languages and grammars

From Wikipedia, the free encyclopedia

I disagree with Tyler McHenry's version of this table, and much prefer the earlier one by Chris Pressey. An unrestricted grammar as defined in the Chomsky hierarchy is well defined and explicit. Listing it for both the Turing Machine and Decider rows seems to imply that both are equivalent. I'm co-teaching a formal languages course this semster, and all the students found this table confusing when "unrestricted" is listed in multiple rows. Jim Mahoney 19:09, 27 March 2006 (UTC)

[edit] Formal languages and grammars vs. Chomsky hierarchy

Since this template is about formal languages and grammars in general, and not strictly the Chomsky hierarchy (as specified in Chomsky (1959, 1963)), would anyone have a problem if we listed other well-documented proper subset formal languages and grammars that have been discovered since then? For example, indexed languages & grammars have been around since Aho (1968) and have been well studied since then, in e.g. Hopcroft & Ullman (1979), not to mention mildly context-sensitive (Joshi et al, 1975), deterministic context-free, and other major formal languages and grammars. –jonsafari 03:37, 21 September 2006 (UTC)

Yes, this table is too heavily tied up in the Chomsky hierarchy — an important classification scheme, to be sure, but not a good way of organizing the information this template needs to convey, seeing as this template needs to include many other kinds of classifications. Please be bold. :-)   —Ruakh_TALK 03:48, 21 September 2006 (UTC)

[edit] Subsets not proper

As far as I know, indexed grammars and tree adjoining grammars, as well as context-free and deterministic context-free grammars, generate the same language. Therefore they are no proper subsets. Math1985 21:22, 7 August 2007 (UTC)

Where do you get this information from? I get my information from Hopcroft & Ullman (1979:233,390), Partee et al (1990:536-542), and Sipser (1997), not to mention many works by Vijay-Shanker & Weir. Most of these sources are cited in the respective language articles, where they should be. –jonsafari 21:18, 8 August 2007 (UTC)

[edit] Range of Mildly context-sensitive languages

If I understand correctly, the term "mildly context-sensitive languages" refers to a range of languages broader than the TAL/LIL and EPDA (= L2 in Weir's Control Language Hierarchy). I'm referring to Joshi, Vijay-Shanker and Weir's "The Convergence of Mildly Context-Sensitive Grammar Formalisms" and Weir's "A Geometric hierarchy beyond context-free languages".--Ippei (talk) 16:13, 21 April 2008 (UTC)

If you would like to contribute this information in mildly context-sensitive languages, please do, always citing your reliable sources specifically. –jonsafari (talk) 06:25, 24 April 2008 (UTC)

I will definitely add there mention to Control Language Hierarchy when I get some time. Meanwhile, the mildly context-sensitive language article already says TAL alone is not the MCSL. It kind of bothers me the mismatch in this template and wondering if anyone could come up with an alternative. Fortunately (Weir 1992) has extended EPDA for his hierarchy in the same name. It's just that TAG not corresponding well to the MCSLs (or maybe the language column should be TAL).--Ippei (talk) 21:36, 3 May 2008 (UTC)

If TAL's are indeed a proper subset of MCSL's, then both rows should appear in this template. –jonsafari (talk) 01:57, 5 May 2008 (UTC)

That's a good point. The four weakly equivalent grammars (TAG,CCG,LIG,HG) indeed defines the language which Weir's Control Language Hierarchy calls Level-2 (Level-1 is CFL). The properties of Level-k (for some finite k>1) corresponds well with the "rough" definition of MCSL by Joshi. Probably the problem is MCSL not defined in a very proper way, as such does not fit very well into this table. --Ippei (talk) 14:15, 5 May 2008 (UTC)

I've edited the table minimally reflecting the facts but keeping the convenience. Hope it's the right way to deal with it. --Ippei (talk) 22:27, 8 May 2008 (UTC)