Formal Languages, Encodings, and Decision Problems

Let $\mathrm{\Sigma }$ be a finite set, called an alphabet. For each natural number $n$, a word of length $n$ over $\mathrm{\Sigma }$ is a function $w:n\to \mathrm{\Sigma }$, equivalently an element of ${\mathrm{\Sigma }}^n$ (The set $B^A$ of all functions $A\to B$). Writing $w(i)=a_i$ for $i<n$, we display the word as $a_0{a}_1\cdots a_{n-1}$. This is the same finite-word convention already used in Finite words, contiguous factors, avoidance and proper-prefix states.

The unique word of length $0$ is the empty word $\epsilon$.

If $u:m\to \mathrm{\Sigma }$ and $v:n\to \mathrm{\Sigma }$ are words, their concatenation is the word $uv:(m+n)\to \mathrm{\Sigma }$ defined by $(uv)(i):=\{\begin{array}{ll}u(i),& i<m,\\ v(i-m),& m\le i<m+n\mathrm{.}\end{array}$

The set of all finite words over $\mathrm{\Sigma }$ is ${\mathrm{\Sigma }}^{\ast }:={\bigcup }_{n\in \mathbb{N}}{\mathrm{\Sigma }}^n,$ an indexed union in the sense of ${\bigcup }_{i\in I}{A}_i:=\bigcup \{A_i:i\in I\}$, and ${\bigcap }_{i\in I}{A}_i:=\bigcap \{A_i:i\in I\}$ for $I\mathrm{\ne }\mathrm{\varnothing }$.

• A word is an element of ${\mathrm{\Sigma }}^{\ast }$, not a subset of $\mathrm{\Sigma }$. The symbols of the alphabet are the values of the function; the word itself is the whole finite sequence.

• For the binary alphabet $\{0,1\}$ the notation $\{0,1{\}}^{\ast }$ means every finite binary word, including $\epsilon$.

Let $\mathrm{\Sigma }$ be a finite alphabet. The word convention of Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$ and the published convention of Finite words, contiguous factors, avoidance and proper-prefix states describe the same words of each length, the same empty word, and the same displayed concatenation of finite words. Hence the set ${\mathrm{\Sigma }}^{\ast }$ on this page is exactly the set of finite words over $\mathrm{\Sigma }$ already used in the published item.

Let $\mathrm{\Sigma }$ be an alphabet. A language over $\mathrm{\Sigma }$ is a subset $L\subseteq {\mathrm{\Sigma }}^{\ast }$, where ${\mathrm{\Sigma }}^{\ast }$ is the set of finite words of Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$ and $\subseteq$ is the subset relation of Subset $x\subseteq y$, proper subset $x⊊y$, and the separation notation $\{z\in x:\phi (z)\}$.

Thus a language is a set of words over a fixed alphabet, not a set of alphabet symbols.

• The ambient alphabet matters. The same set of written strings can be viewed as a language over different alphabets only when it is contained in each corresponding ${\mathrm{\Sigma }}^{\ast }$.

• The two extreme languages over $\mathrm{\Sigma }$ are $\mathrm{\varnothing }$ and ${\mathrm{\Sigma }}^{\ast }$.

Fix an alphabet $\mathrm{\Sigma }$, and let $L,K\subseteq {\mathrm{\Sigma }}^{\ast }$ be languages over $\mathrm{\Sigma }$ (Languages over an alphabet).

Their union, intersection, and difference are the languages $L\cup K,L\cap K,L\setminus K\mathrm{.}$

Their complement is taken inside the same ambient ${\mathrm{\Sigma }}^{\ast }$: $L^c:={\mathrm{\Sigma }}^{\ast }\setminus L\mathrm{.}$

• Complement depends on the chosen ambient alphabet. A language may have different complements when it is regarded inside different ${\mathrm{\Sigma }}^{\ast }$.

• These are ordinary set-theoretic operations applied to subsets of ${\mathrm{\Sigma }}^{\ast }$.

Fix an alphabet $\mathrm{\Sigma }$, and let $L,K\subseteq {\mathrm{\Sigma }}^{\ast }$ be languages over $\mathrm{\Sigma }$ (Languages over an alphabet).

Their concatenation is $LK:=\{uv:u\in L\text{ and }v\in K\},$ where $uv$ is word concatenation as in Computation alphabets, words, the empty word, and ${\mathrm{\Sigma }}^{\ast }$.

Define the powers of $L$ by $L^0:=\{\epsilon \}$ and, for each $n\ge 1$, let $L^n$ be the set of words of the form $u_1{u}_2\cdots u_n$ with each $u_i\in L$.

The Kleene star of $L$ is $L^{\ast }:={\bigcup }_{n\in \mathbb{N}}{L}^n\mathrm{.}$

• The word $\epsilon$ belongs to $L^{\ast }$ for every language $L$, even when $L=\mathrm{\varnothing }$, because it already lies in $L^0$.

• The positive closure $L^{+}:={\bigcup }_{n\ge 1}{L}^n$ satisfies $L^{\ast }=L^{+}\cup \{\epsilon \}$.

For languages $L_1,L_2,L_3$ over the same alphabet, $(L_1{L}_2)L_3=L_1(L_2{L}_3)\mathrm{.}$

Let $L$ be a language over an alphabet $\mathrm{\Sigma }$.

1. $\epsilon \in L^{\ast }$.
2. $L{L}^{\ast }\subseteq L^{\ast }$.
3. If $K$ is a language with $\epsilon \in K$ and $LK\subseteq K$, then $L^{\ast }\subseteq K$.

In particular, $L^{\ast }$ is the least language containing $\epsilon$ and closed under left concatenation by words from $L$; therefore it is also the least concatenation-closed language containing $L$ and $\epsilon$.

Let $w:n\to \mathrm{\Sigma }$ be a word over an alphabet $\mathrm{\Sigma }$. Its reversal is the word $w^R:n\to \mathrm{\Sigma }$ defined by $w^R(i):=w(n-1-i)(i<n)\mathrm{.}$ Equivalently, if $w=a_0{a}_1\cdots a_{n-1}$, then $w^R=a_{n-1}{a}_{n-2}\cdots a_0$. In particular, ${\epsilon }^R=\epsilon$.

If $L\subseteq {\mathrm{\Sigma }}^{\ast }$ is a language, its reversal is $L^R:=\{w^R:w\in L\}\mathrm{.}$

• Reversal changes the order of letters but not the alphabet or the word length.

• The definition is pointwise on words first and only then lifted to languages.

For words $u,v$ over a fixed alphabet and languages $L,K$ over that alphabet:

1. $(uv{)}^R=v^R{u}^R$.
2. $(w^R{)}^R=w$ for every word $w$.
3. $(LK{)}^R=K^R{L}^R$ and $(L^R{)}^R=L$.

Let $\mathrm{\Sigma }$ and $\mathrm{\Delta }$ be alphabets. An alphabet map is a function $h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{\ast }$ in the sense of A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain.

Its induced word map is the function $\widehat{h}:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Delta }}^{\ast }$ defined as follows. For the empty word, $\widehat{h}(\epsilon )=\epsilon$. For a one-letter word $w=a_0$, set $\widehat{h}(w):=h(a_0)$. For a word $w=a_0{a}_1\cdots a_{n-1}$ of length $n\ge 2$ over $\mathrm{\Sigma }$, set $\widehat{h}(w):=(\cdots ((h(a_0)h(a_1))h(a_2))\cdots h(a_{n-1})),$ the left-associated concatenation of the image words of its letters.

• When every $h(a)$ has length $1$, the induced map simply replaces each letter $a$ by a single letter $h(a)$.

• The point of the definition is that the whole map on ${\mathrm{\Sigma }}^{\ast }$ is determined by the values on the letters of $\mathrm{\Sigma }$.

Let $h:\mathrm{\Sigma }\to {\mathrm{\Delta }}^{\ast }$ be an alphabet map and let $\widehat{h}:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Delta }}^{\ast }$ be its induced word map. For $a\in \mathrm{\Sigma }$, write $⟨a⟩:1\to \mathrm{\Sigma }$ for the one-letter word whose unique value is $a$.

1. For all words $u,v\in {\mathrm{\Sigma }}^{\ast }$, $\widehat{h}(uv)=\widehat{h}(u)\widehat{h}(v)\mathrm{.}$
2. If $g:{\mathrm{\Sigma }}^{\ast }\to {\mathrm{\Delta }}^{\ast }$ satisfies $g(uv)=g(u)g(v)$ for all words $u,v$ and $g(⟨a⟩)=h(a)$ for every $a\in \mathrm{\Sigma }$, then $g=\widehat{h}$.

Let $\mathbb{B}:=\{0,1\}$. A binary encoding of a set $X$ is an injective function $e:X\to {\mathbb{B}}^{\ast }$ (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain, Injection, surjection, bijection).

Fix a symbol $\mathtt{m}\mathtt{a}\mathtt{l}$ not belonging to $X$. A total decoder for $e$ is a function $d:{\mathbb{B}}^{\ast }\to X\cup \{\mathtt{m}\mathtt{a}\mathtt{l}\}$ such that $d(e(x))=x(x\in X),d(w)=\mathtt{m}\mathtt{a}\mathtt{l}(w\mathrm{\notin }e[X])\mathrm{.}$ Thus $\mathtt{m}\mathtt{a}\mathtt{l}$ is exactly the output on malformed codes, and the decoder is defined on every binary word, not only on words in the image of $e$.

The encoding $e$ is effective when such a total decoder is specified.

The encoding is prefix-free when no codeword is a proper prefix of another: there do not exist distinct $x,y\in X$ and a nonempty binary word $u$ with $e(y)=e(x)u$.

• Effectiveness here means injective plus explicitly decodable with a fixed malformed-code output. It does not yet formalize computation by Turing machines.

• Prefix-freeness is an additional property, not part of the definition of an effective encoding.

For every fixed $k\ge 1$, the set of binary $k$-tuples $(w_1,\dots ,w_k)\in (\{0,1{\}}^{\ast }{)}^k$ has an effective prefix-free binary encoding.

Fix a set $I$ of instances together with an effective binary encoding $\sigma :I\to \{0,1{\}}^{\ast }$ (Effective binary encodings and total decoders).

A decision problem on $I$ is a distinguished subset $Y\subseteq I$ of yes-instances. Its associated language of encoded yes-instances is $L_{\sigma }(Y):=\{\sigma (x):x\in Y\}\subseteq \{0,1{\}}^{\ast },$ a language over the binary alphabet in the sense of Languages over an alphabet.

A search problem on $I$ consists of a condition assigning to each instance $x\in I$ a set of acceptable outputs; solving the problem means producing one acceptable output when one exists.

A function problem on $I$ is a specified total function on instances, $f:I\to O,$ for some output set $O$ (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain).

• Decision problems ask for a yes/no answer, search problems ask for a witness, and function problems ask for a designated output value.

• The same mathematical problem can have several encodings. The associated language depends on the chosen $\sigma$.

Let $I$ be a set of instances and let $\sigma :I\to \{0,1{\}}^{\ast }$ be an effective binary encoding. The size of an instance $x\in I$ with respect to $\sigma$ is the length of its codeword: $\mathrm{\mid }x{\mathrm{\mid }}_{\sigma }:=\mathrm{\mid }\sigma (x)\mathrm{\mid }\mathrm{.}$

If $\sigma ,\tau :I\to \{0,1{\}}^{\ast }$ are two effective encodings of the same instance set, they are polynomially related when there exist polynomials $p,q:\mathbb{N}\to \mathbb{N}$ such that for every $x\in I$, $\mathrm{\mid }\sigma (x)\mathrm{\mid }\le p(\mathrm{\mid }\tau (x)\mathrm{\mid })\text{and}\mathrm{\mid }\tau (x)\mathrm{\mid }\le q(\mathrm{\mid }\sigma (x)\mathrm{\mid })\mathrm{.}$

• Resource bounds are measured as functions of encoded input length, not of an abstract instance before encoding.

• Polynomially related encodings may differ substantially, but neither can blow up the other's lengths by more than a polynomial factor.

Let $\sigma ,\tau :I\to \{0,1{\}}^{\ast }$ be polynomially related encodings of the same instance set $I$. For any function $m:I\to \mathbb{N}$, the following are equivalent:

1. There is a polynomial $p$ such that $m(x)\le p(\mathrm{\mid }x{\mathrm{\mid }}_{\sigma })$ for every $x\in I$.
2. There is a polynomial $r$ such that $m(x)\le r(\mathrm{\mid }x{\mathrm{\mid }}_{\tau })$ for every $x\in I$.

False claim: if $\mathrm{\Sigma }$ is an alphabet, then every language over $\mathrm{\Sigma }$ is a subset of $\mathrm{\Sigma }$.

False claim: every effective binary encoding is prefix-free.