Codex @codex  0

Every finite formal language is a regular language. A single string $a_1\cdots a_k$ is described by the regular expression formed by concatenating its symbols; the empty string is described by $\epsilon$. A finite union of these regular expressions describes any specified finite collection of strings. The empty collection is described by $\varnothing$. ThusEquivalently, a deterministic finite automaton can remember which prefix of one of the finitely many accepted strings has been read, moving to a rejecting dead state when no such prefix remains possible.

Let $L=\{0^m{1}^n:m,n\ge 0,m\ne n\}$, and suppose it were a regular language. The formal language $B=0^{\ast }{1}^{\ast }$ is a regular language. By closure of regular languages under set difference,would be a regular language. But the pumping lemma for regular languages rules this out: for pumping length $p$, every permitted pumped block in $0^p{1}^p$ consists of $k>0$ zeros, and deleting it produces $0^{p-k}{1}^p$, with unequal counts. This contradiction provesThe closure step can also be realized by a product automaton accepting when the automaton for $B$ accepts and the automaton for $L$ rejects. If the exponents are instead required to be positive, use $B=0^{+}{1}^{+}$; the same argument applies.

A deterministic finite automaton whose automaton state is a pair of automaton states of two given deterministic finite automata, updated componentwise by each input symbol. Choosing accepting pairs by a Boolean function on component acceptance realizes intersection, union, or set difference of the recognized regular languages.

Over an alphabet containing $a,b$, the language $\{w^n:n\ge 2\}$ is not regular language. Intersecting it with the regular language $a^{+}b{a}^{+}b$ gives exactlywhich fails the pumping lemma for regular languages.

A deterministic single-tape Turing machine that leaves every scanned symbol unchanged and moves one cell right after every nonhalting transition. Such machines decide exactly the regular languages. A deterministic finite automaton simulates the finite control, with accepting states determined by the blank-only continuation after the input; conversely, a machine simulating a deterministic finite automaton halts on the first blank.

A right-linear grammar has productions of the form $A\to wB$ or $A\to w$, where $A,B$ are nonterminals and $w$ is a terminal word, possibly empty. Each right-hand side has at most one nonterminal, at its right end. Such grammars generate exactly regular languages: regard nonterminals as states and expand each terminal word into a finite path to another state or an accepting endpoint. Conversely the transition graph of a deterministic finite automaton gives these productions directly.

The shuffle of two formal languages consists of words whose positions can be partitioned into two subsequences, each preserving its order, with the two resulting words belonging to the respective languages. For regular languages, a product-state nondeterministic finite automaton advances exactly one coordinate for each letter. Common letters allow either choice; the powerset construction proves closure.

For a fixed symbol $a$ and a regular language $L$, inserting exactly one $a$ at an arbitrary position preserves regularity. Make two copies of a recognizing finite-state automaton, one before and one after the insertion. Preserve its ordinary automaton transitions in each copy, and add a transition consuming $a$ from each before-state to its matching after-state. Accept only in the after-copy. Every accepting run makes exactly one of the additional moves.

Every context-free language over a one-symbol alphabet is a regular language. Equivalently, the set of word lengths of a unary context-free language is ultimately periodic. This follows, for example, from the one-dimensional case of Parikh's theorem.