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: 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)
  • Re: 2.7% world market share
    ... I find that people like you like to snip out context so that they can ... several occasions, You fail to read threads in their entirety, which leads ... you to argue something far removed from the context of the thread. ... "If you raise the ceiling four feet, move the fireplace from that wall ...
    (comp.sys.mac.advocacy)