wiki_research

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

parikh_image (744B)


      1 # Parikh image
      2 
      3 The *Parikh image* of a [word] is the [vector] of the number of occurrences of the letters that it contains, and the *Parikh image* of a [formal_language] is the set of Parikh images of the [words] that it contains
      4 
      5 [Parikhs_theorem]: the Parikh images of [CFLs] and of [regular_languages] are the same!
      6 
      7 The Parikh image is not always [recognizable] even for a [regular_language]
      8 - https://cstheory.stackexchange.com/questions/46670/languages-whose-parikh-image-is-recognizable
      9 - it relates to [regular_languages] whose [commutative_closure] is also a [regular_language]
     10   - cf [commutative_closure_does_not_preserve_regularity]
     11 
     12 Up: [formal_language_theory]
     13 
     14 See also: [language_commutative], [length]
     15 
     16 Aliases: parikh images