wiki_research

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

context_free_grammar_linear (569B)

      1 # Context free grammar linear
      2 
      3 https://en.wikipedia.org/wiki/Linear_grammar
      4 
      5 [Computational_problems]:
      6 - [linear_CFG_universality]
      7 - [linear_CFG_equivalence]
      8 - Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
      9 
     10 By [Greibach's_theorem], it is undecidable whether an input [CFG] recognizes a [linear_CFL]
     11 
     12 Up: [context_free_grammar]
     13 
     14 Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars, linear CFG, linear CFGs
     15 
     16 See also: [context_free_language_linear]