wiki_research

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

context_free_language (859B)

      1 # Context free language
      2 
      3 [language] accepted by [context_free_grammar]
      4 
      5 - [context_free_language_membership]
      6 - [context_free_language_slender]
      7 - [context_free_language_polyslender]
      8 
      9 Subclass: [context_free_language_subclasses]
     10 
     11 - [context_free_language_unambiguous]
     12 - [context_free_language_deterministic]
     13 - [context_free_language_linear]
     14 - [context_free_language_deterministic_linear]
     15 - [context_free_language_unambiguous_linear]
     16 
     17 Variants:
     18 
     19 - CFL [cap] [coCFL]:
     20   - contains [DCFL]
     21   - also contains [palindrome_language]
     22     - https://cstheory.stackexchange.com/a/4264
     23   - testing membership is [undecidable]
     24     - https://cstheory.stackexchange.com/a/20727
     25 - CFL [cup] [coCFL]:
     26   - https://cstheory.stackexchange.com/q/9098
     27 
     28 Up: [language], [context_free_grammar]
     29 
     30 Aliases: context-free languages, context free languages, context-free language, CFL, CFLs