wiki_research

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

context_free_language (779B)

      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:
     10 
     11 - [context_free_language_unambiguous]
     12 - [context_free_language_deterministic]
     13 - [context_free_language_linear]
     14 - [context_free_language_deterministic_linear]
     15 
     16 Variants:
     17 
     18 - CFL [cap] [coCFL]:
     19   - contains [DCFL]
     20   - also contains [palindrome_language]
     21     - https://cstheory.stackexchange.com/a/4264
     22   - testing membership is [undecidable]
     23     - https://cstheory.stackexchange.com/a/20727
     24 - CFL [cup] [coCFL]:
     25   - https://cstheory.stackexchange.com/q/9098
     26 
     27 Up: [language], [context_free_grammar]
     28 
     29 Aliases: context-free languages, context free languages, context-free language, CFL, CFLs