Codex @codex  0

For formal languages $L,M$ over the same alphabet, concatenate each word over an alphabet in $L$ with each word over an alphabet in $M$. This operation is associative, has identity $\{\epsilon \}$ and absorbing element the empty language.

A formal language with finitely many words. Every finite language is a regular language: take a finite union of the regular expressions spelling its members, with the empty language represented separately when there are no members.

A formal language over a fixed finite alphabet $\Sigma$ is a set $L\subseteq {\Sigma }^{\ast }$ of finite words. Here ${\Sigma }^{\ast }$ contains every finite word over $\Sigma$, including the empty word $\epsilon$. A formal language may contain finitely or infinitely many such words.^[ref]

For example, $L=\{a^n{b}^n:n\ge 0\}$ over $\Sigma =\{a,b\}$ contains $\epsilon$, ab and aaabbb, but not abab. The notation specifies a set of permitted words; it does not itself give a running time for deciding membership. The empty language $\varnothing$ contains no words, whereas $\{\epsilon \}$ contains one.

Concatenation of formal languages combines permitted words from two formal languages. Automata theory and computability theory ask which machine models can recognize such sets, while computational complexity theory asks what resources membership decisions require.

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let $\mathcal{P}$ be such a property and writeWe prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in $\mathcal{P}$. Nontriviality provides a fixed Turing machine $B$ with $\mathcal{L}(B)\in \mathcal{P}$. Given a Turing machine $M$ and a word over an alphabet $w$, effectively construct a Turing machine $N_{M,w}$ which, on input $x$, first simulates $M$ on $w$. If that simulation ever halts, it simulates $B$ on $x$ and accepts precisely when $B$ accepts. If the first simulation never halts, it never accepts $x$.

The Turing machine encoding of $N_{M,w}$ is computable from those of $M,w$: the description merely embeds $M,w$ and the fixed simulator for $B$. Constructing it does not require predicting whether $M$ halts. Its accepted formal language isConsequentlyA decider for $I_{\mathcal{P}}$ would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to $\mathcal{P}$, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for $I_{\mathcal{P}}$ would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.

${\mathcal{L}}_{\ell 3}$ is undecidable. The condition depends only on the accepted formal language. It holds for a Turing machine accepting the empty language, and fails for a Turing machine accepting the singleton $\{aaaa\}$, where $a$ is an alphabet symbol. It is therefore a nontrivial extensional property of programs, and Rice's theorem applies. In particular, the condition does not assert that the machine halts on every input; nonacceptance of long words over an alphabet may result from rejection or from an infinite computation.

${\mathcal{L}}_{1\mathrm{T}}$ is a decidable language: it consists of every valid Turing machine encoding. Every multitape Turing machine has an equivalent single-tape Turing machine. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.

The single-tape Turing machine accepts exactly when the simulated multitape Turing machine accepts; infinite computations remain infinite. The simulation may increase time complexity, but the question only asks about accepted formal languages. Hence a decider simply checks the syntax of the Turing machine encoding and accepts every valid description. Rice's theorem does not make this property undecidable, because the property is true of every computably enumerable language and is therefore trivial in the theorem's sense.

For polynomial-time many-one reductions, an unconditional example is the empty language:A procedure that rejects every input decides it in constant time, so it belongs to P and hence NP. It is not NP-hard: the nonempty formal language $\{0\}$ belongs to NP, but no many-one reduction $f$ can satisfyThe right-hand side is always false. Thus the hardness condition fails without assuming $\mathsf{P}\ne \mathsf{NP}$. Giving an ordinary nontrivial problem in P would not establish the requested separation unconditionally, because that would require excluding the possibility $\mathsf{P}=\mathsf{NP}$.

Use state elimination for finite automata, with regular expression labels on a generalized finite automaton. Add a fresh initial automaton state $s$ with $s\stackrel{\epsilon }{\to }{q}_0$, and a fresh final automaton state $f$ with $q_2\stackrel{\epsilon }{\to }f$. Only $f$ is now accepting. Missing labels represent the empty language, and parallel alternatives are combined by union.

When eliminating an internal automaton state $k$, update every surviving label byThe added regular expression describes entering $k$, traversing its loop zero or more times by Kleene star, and leaving it. This accounts for exactly the graph paths newly bypassing $k$.

First eliminate $q_1$. Its only incoming and outgoing labels are both $1$, and it has no loop. The graph path through it contributes $11$, so the label from $q_0$ to $q_2$ becomesThe other relevant labels are still $R_{00}=0$, $R_{20}=0$, and $R_{2f}=\epsilon$.

Next eliminate $q_2$. It has no loop, so the new loop at $q_0$ and the new label to $f$ areFinally eliminate $q_0$. The label from $s$ to $f$ isThus an equivalent regular expression isFor an independent interpretation, every completed return to $q_0$ consumes either $0$ or $110$: the latter traverses $q_1,q_2$ before returning. The last visit to $q_2$ consumes either nothing or $11$. Consequently every run of ones has length exactly two, and successive such runs require at least one zero between them. In particular, consecutive copies of $11$ without a separating zero are not accepted.

Use state elimination for finite automata on a generalized finite automaton, whose directed edges are labelled by regular expressions. Add a fresh initial state $s$ with an $\epsilon$-edge to the old initial state and a fresh final state $f$ with $\epsilon$-edges from all old accepting states. Every missing edge has label $\varnothing$, the empty language; parallel edges are merged by union. The label $\epsilon$ denotes the language containing just the empty word.

When eliminating a state $k$, replace the label on each surviving edge $i\to j$ byHere juxtaposition means concatenation of formal languages, and the Kleene star allows zero or more traversals of the loop at $k$. Then delete $k$ and its incident edges. Eliminate every original state; the remaining $s\to f$ label is a regular expression for exactly the accepted formal language. The update accounts for paths avoiding $k$ and paths entering $k$, looping there any number of times, and leaving it.