I'm considering the problem of recognizing a language (over alphabet 0-9 and space) containing strings like "1 2 3 4 5 6" and "14 15 16 17" but not "1 3".

This came up while working on a common parsing task where elements needed to be in an ordered list. It struck me that while parsing the rest of that language was regular, this part was clearly irregular -- it can recognize, for example, the language A1A2 where A is an arbitrary string 0-9. In fact it seems to be content-sensitive (and not context-free by the pumping lemma).

My first question: is there a (reasonably well-known, i.e. not defined just for this problem) class of languages between context-sensitive and context-free that describes its expressive power better? I've read about Aho's indexed languages, but it's not obvious (to me!) that these are even in that class, powerful though it is.

My second question is informal. It seems that this language is easy to parse, and yet it is very high on the hierarchy. Is it common to come across similar examples and is there a standard way of dealing with them? Is there an alternate grouping of classes of languages that is incompatible with inclusion on the 'usual' ones?

My reason for thinking this is easy: the language can be parsed deterministically, by reading until you get to the end of the first number, checking if the next number follows, and so forth. In particular it can be parsed in O(n) time with O(n) space; the space can be reduced to $O(\sqrt n)$ without too much trouble, I think. But it's hard enough to get that kind of performance with regular languages, let alone context-free.

  • $\begingroup$ The pumping lemma is used to discriminate context-free languages from regular languages and not from context-sensitive languages. So it is sure that your language is not regular, but I think it could be context-free... $\endgroup$ – Benoît Fraikin Jun 30 '11 at 2:20
  • 2
    $\begingroup$ @Benoît Fraikin: I'm using 'the other' pumping lemma. $\endgroup$ – Charles Jun 30 '11 at 2:26
  • $\begingroup$ The Bar-Hillel lemma... this is my misunderstanding ^_^ $\endgroup$ – Benoît Fraikin Jul 3 '11 at 17:29

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some interesting surveys on this language hierarchy, such as

Marek Chrobak: Hierarchies of one-way multihead automata, http://www.sciencedirect.com/science/article/pii/0304397586900939

This also gives one answer to your second question: The hierarchy of n-head automata lies "across" the Chomsky hierarchy.

  • $\begingroup$ That's really fantastic. I'm surprised -- and pleased -- to see the existence of such a class. $\endgroup$ – Charles Jun 30 '11 at 16:21
  • 3
    $\begingroup$ @Marek is on this site: maybe he will weigh in :) $\endgroup$ – Suresh Venkat Jun 30 '11 at 21:39
  • 3
    $\begingroup$ That paper was written in my previous life ;-) Yes, if I understand the problem, this language can be accepted by a one-way 2-head automaton. So it's also in LOGSPACE. $\endgroup$ – Marek Chrobak Jul 3 '11 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.