Limits of regular languages

e0726905 <e0726905@student.tuwien.ac.at>
Thu, 11 Feb 2010 22:36:06 +0100

          From comp.compilers

Related articles
Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-11)
Re: Limits of regular languages ott@mirix.org (Matthias-Christian Ott) (2010-02-13)
Re: Limits of regular languages kkylheku@gmail.com (Kaz Kylheku) (2010-02-13)
Re: Limits of regular languages cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13)
Re: Limits of regular languages max@gustavus.edu (Max Hailperin) (2010-02-13)
Re: Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-27)
| List of all articles for this month |

From: e0726905 <e0726905@student.tuwien.ac.at>
Newsgroups: comp.compilers
Date: Thu, 11 Feb 2010 22:36:06 +0100
Organization: Compilers Central
Keywords: lex, question
Posted-Date: 13 Feb 2010 11:33:13 EST

Hi,


I have been playing around with regular expressions for the last few
weeks, implementing the automaton generation algorithms from the dragon
book and taking at the existing tools.
Now a few questions have sprung, that I haven't been able to answer:


Is there a way implement the usual longest-match behaviour of a scanner
with a DFA without any backtracking mechanisms, meaning is that
behaviour strictly regualr or not?


I know that backreferences make a language non-regular (more about that
later), but what forms of capture are regualr? Are there any tools out
there who always answer membership in O(n) that support some kind of
subexpression capture? (Without having to hack around yourself with
embedded actions.)


I also have two rather unrelated questions that have been bugging me for
quite some time:


Is every regular language LL(1)? I know that every regular language is a
    context-free language, and that every LL(1) language is also
context-free. But are all regular languages contained in LL(1)?


What class of language do regexes with backreferences fall into?
Membership is NP-Complete so they are not in CFG (or are they? assuming
P=NP?).


thanks, fabian



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.