Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I'd like to know if there is a way to determine if a context-free grammar can be converted to

  • a LL(1) grammar
  • a LL(k) grammar, whatever the value of k (so the algorithm should give the value of k)

By "can be converted to", I mean that the new (LL) grammar must generate the same language as the old grammar.

If it can't be done, I'd appreciate some references. I'm also interested in ways to achieve the same result under more restrictive conditions (for instance only for non-ambiguous context-free grammars).

I'd also like to know if there a way to check if a grammar is LL(k), irrespective of the k, so I wouldn't have to iterate on the value of k.

share|improve this question
1  
Crossposted on math.SE; should probably rather be on cs.SE? – Raphael Jun 8 '12 at 19:17
Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. – Kaveh♦ Jun 8 '12 at 19:49
It also appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy only permits a repost after sufficient time has passed and you have not obtained the desired answer elsewhere. I am closing the question since simultaneous crossposting duplicates effort and fractures discussion. Please wait a few days and then if your question is still not answered request a reopening by flagging the question for moderator attention (after summarizing relevant discussions from other sites). – Kaveh♦ Jun 8 '12 at 19:49
Sorry for the cross-posting I guess. About research-level, well I haven't found references to any of the algorithms I ask about. So they may very well be research-level (and most probably some of them are), and actually, knowing if they are is kind of the point here. – Norswap Jun 8 '12 at 22:02

closed as not constructive by Tsuyoshi Ito, Kaveh♦ Jun 8 '12 at 19:49

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or specific expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, see the FAQ for guidance.