What is this generalization of formal grammar called?

March 26, 2017 10:43 AM

I have been reading a little about formal grammar in the context of computer language parsing. I understand that a formal grammar G is defined as the tuple (N, Σ, P, S), where N are nonterminal symbols, Σ are terminal symbols, P are production rules, and S is the start symbol. N, Σ, and P are all finite sets. But what is it called if they're infinite?

It seems like a relatively obvious generalization to relax this part of the definition, to allow for nonterminal symbols with production rules like A(x)→yA(xy). This seems like a handy way to represent aspects of certain context-sensitive grammars, like Python-style "offside rule" indentation. I imagine there's probably a proof that any "grammar" of this sort has at least a weakly-equivalent formal grammar with a finite number of nonterminals and production rules, but it still seems potentially advantageous to be able to write (certain) context-sensitive grammars analogously to the more typical context-free form.

This seems like an obvious question to ask, so I'm sure someone must have addressed this back in the 1960's or 1970's, but since I'm only a dilettante in this field with no formal (pun intended) training I don't quite know what to look for. Any help pointing me in the right direction would be greatly appreciated!

posted by biogeo to Science & Nature (7 answers total)

You call them non-context-free languages.
Hie thee to the Pumping Lemma.

Perhaps you might look at Infinite Grammars and Infinite Languages.
posted by the Real Dan at 10:59 AM on March 26, 2017 [1 favorite]

Here's some answers I found just looking around on line. I wonder if there is a theorem that a language with an infinite set of terminal symbols can be written as one with a finite set of symbols and a second grammar mapping each such symbol to infinite sets.
posted by Obscure Reference at 11:03 AM on March 26, 2017 [1 favorite]

You could use a grammar like this to describe any formal language:

Define a single nonterminal A which is also the start symbol. The production rules are: for every word in the language, "A → <word>".
posted by panic at 11:09 AM on March 26, 2017 [1 favorite]

Response by poster: Thanks for the answers so far. For the purposes of this question, I'm actually interested more in the properties of the formal grammar than in the properties of the language it describes.

the Real Dan, revisiting the Pumping Lemma led me to the term "indexed grammar," which describes exactly what I was looking for. Thanks!
posted by biogeo at 1:16 PM on March 26, 2017

I have spent many hours of my life pumping llamas. In the context of computer languages, I believe there is no such thing as a contextual language (all languages are context free languages). When I took my compilers class as an undergrad I spent some time looking into infinite grammers and couldnt find any specific instances. If you find something I would be very interested!
posted by KeSetAffinityThread at 9:10 PM on March 26, 2017

I know the logic and linguistics here, and only that a bit. But people like David Lewis (General Semantics) and Richard Montague were concerned related issues in the early 70s.

Maybe have a gander at the Gamut volume on this stuff and follow references. The Lewis paper is from Semantics and Phil Lang from 1972, and it has other relevant stuff in it. Perhaps Partee's book from 1990 on this stuff, too.

If none of this helps, well, good luck and I tried!
posted by persona au gratin at 2:12 AM on March 27, 2017 [1 favorite]

> In the context of computer languages, I believe there is no such thing as a contextual language (all languages are context free languages).

Nope, both C and C++ are not context free languages, for example.
See http://trevorjim.com/c-and-cplusplus-are-not-context-free/ and http://stackoverflow.com/questions/14589346/is-c-context-free-or-context-sensitive for more info
posted by richb at 3:19 AM on March 27, 2017 [2 favorites]