wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

context_free_grammar_membership (336B)


      1 # Context free grammar membership
      2 
      3 Given a [CFG] G and a [word] w, decide whether w is accepted by G
      4 
      5 Can be studied in:
      6 - [combined_complexity]
      7   - can do [CFG_parsing] like [CYK]
      8 - [data_complexity]: cf [context_free_language_membership]
      9 
     10 Up: [context_free_grammar], [membership_problem]
     11 
     12 See also: [context_free_language_membership]