Context free languages

Hallo,

is there a simple argument to show that the word problem for context-
free languages is in P?

I can argue that the word problem of context sensitive ones is in
NSPACE but I have no idea what to do with the context-free ones.

Thanks,
S.
.

Relevant Pages

  • Re: Word problems for grammars
    ... What about the type 1 word problem (context sensitive ... languages), ... Is there any meaningful formulation of the complexity of the problem ...
    (comp.theory)
  • Re: Context free languages
    ... is there a simple argument to show that the word problem for context- ... free languages is in P? ... I can argue that the word problem of context sensitive ones is in ... Oh, sorry, this is the CYK algorithm. ...
    (comp.theory)
  • Re: XP license to 2nd computer legal?
    ... Taking a statement completely out of context as ... say that all he wants to do is argue, ... and inconvenient facts in order to win. ... mayayana's 'complaint' is that I had the audacity to post some facts and opinions he/she apparently didn't like but which ones they are we may never know as they made no reply to them before going on their 'complaint' campaign. ...
    (alt.comp.hardware.pc-homebuilt)
  • Re: Roger Ebert comes out of the closet!!
    ... that it doesnt actually state when taken in context. ... argue with me"? ... anything with which you disagree to a question of religion ... evidence" when i only accept evidence that other rational adults ...
    (talk.origins)
  • Re: Mark Burnett Testifies For Prosecution In Richard Hatch Trial
    ... >> Well I can't argue with that:) ... >rest from context. ... >>>Please point out exactly where I said any of this is unfair. ... No, it's a rhetorical question, not specifically directed at you. ...
    (alt.tv.survivor)