xn1xn

xn1xn denotes the language of strings over the alphabet {x, 1} consisting of n copies of x, followed by a single 1, followed by n copies of x, for n ≥ 0. In formal notation, L = { x^n 1 x^n | n ≥ 0 }. The strings thus have the form x^n 1 x^n and are palindromic around the central symbol 1, with the central 1 serving as a delimiter between the two identical halves.

Properties and recognition: The language is context-free but not regular. It can be accepted by a deterministic pushdown automaton that pushes a symbol for each x read on the left, encounters the central 1 to switch mode, and then pops a symbol for each x on the right, accepting when the input ends with an empty stack. This makes it a classic example used to illustrate deterministic context-free languages.

Examples: For n = 0, the string is 1. For n = 1, it is x1x. For n = 2, it is xx1xx, and so on. All valid strings have exactly n x's on both sides of the central 1.

Variants and related concepts: Variations include replacing x with other alphabet symbols, or allowing a broader set of center symbols, while preserving the symmetrical structure x^n center x^n. The concept relates to broader topics in formal language theory, such as palindrome-like languages and the study of deterministic context-free languages, alongside classic examples like {a^n b^n}.