Editing Palindrome (section)

=== Computation theory ===
In [[automata theory]], a [[set (mathematics)|set]] of all palindromes in a given [[alphabet]] is a typical example of a [[formal language|language]] that is [[context-free language|context-free]], but not [[Regular language|regular]]. This means that it is impossible for a [[finite automaton]] to reliably test for palindromes.

In addition, the set of palindromes may not be reliably tested by a [[deterministic pushdown automaton]] which also means that they are not [[LR parser|LR(k)-parsable]] or [[LL parser|LL(k)-parsable]]. When reading a palindrome from left to right, it is, in essence, impossible to locate the "middle" until the entire word has been read completely.

It is possible to find the [[longest palindromic substring]] of a given input string in [[linear time]].<ref name=Jewels>{{citation
  | last1        = Crochemore
  | first1       = Maxime
  | last2        = Rytter
  | first2       = Wojciech
  | author2-link = Wojciech Rytter
  | title        = Jewels of Stringology: Text Algorithms
  | title-link   = Jewels of Stringology
  | publisher    = World Scientific
  | year         = 2003
  | isbn         = 978-981-02-4897-0
  | contribution = 8.1 Searching for symmetric words
  | pages        = 111–114
}}</ref><ref>{{citation
  | last         = Gusfield
  | first        = Dan
  | contribution = 9.2 Finding all maximal palindromes in linear time
  | doi          = 10.1017/CBO9780511574931
  | isbn         = 978-0-521-58519-4
  | location     = Cambridge
  | mr           = 1460730
  | pages        = 197–199
  | publisher    = Cambridge University Press
  | title        = Algorithms on Strings, Trees, and Sequences
  | year         = 1997
| s2cid = 61800864
 }}</ref>

The '''palindromic density''' of an infinite word ''w'' over an alphabet ''A'' is defined to be zero if only finitely many prefixes are palindromes; otherwise, letting the palindromic prefixes be of lengths ''n''<sub>''k''</sub> for ''k''=1,2,... we define the density to be

:<math> d_P(w) = \left( { \limsup_{k \rightarrow \infty} \frac{n_{k+1}}{n_k} } \right)^{-1} \ . </math>

Among aperiodic words, the largest possible palindromic density is achieved by the [[Fibonacci word]], which has density 1/φ, where φ is the [[Golden ratio]].<ref name=AB443>{{citation
  | last1         = Adamczewski
  | first1        = Boris
  | last2         = Bugeaud
  | first2        = Yann
  | chapter       = 8. Transcendence and diophantine approximation
  | editor1-last  = Berthé
  | editor1-link  = Valérie Berthé
  | editor1-first = Valérie
  | editor2-last  = Rigo
  | editor2-first = Michael
  | title         = Combinatorics, automata, and number theory
  | location      = Cambridge
  | publisher     = [[Cambridge University Press]]
  | series        = Encyclopedia of Mathematics and its Applications
  | volume        = 135
  | page          = 443
  | year          = 2010
  | isbn          = 978-0-521-51597-9
  | zbl           = 1271.11073
}}</ref>

A '''palstar''' is a [[concatenation]] of palindromic strings, excluding the trivial one-letter palindromes – otherwise all strings would be palstars.<ref name=Jewels />