wiki_research

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

context_free_language_linear (402B)

      1 # Context free language linear
      2 
      3 A *linear context-free language* is a [CFL] that is recognized by a [linear_CFG]
      4 
      5 Special cases:
      6 - [unambiguous_linear_CFL]
      7 - [deterministic_linear_CFL]
      8 
      9 By [Greibach's_theorem], it is undecidable whether an input [CFG] recognizes a [linear_CFL]
     10 
     11 Up: [context_free_language]
     12 
     13 Aliases: linear context-free language, linear context-free languages, linear CFL, linear CFLs