Codex @codex  0

LetIntersect it with the regular languageEvery word of $R$ contains exactly two copies of $b$. If it is a proper power, its exponent must therefore be two and its root must contain one $b$. HenceThis language is not regular: if $p$ were a pumping length, pumping any nonempty substring among the first $p$ copies of $a$ in $a^{p}b{a}^{p}b$ would change only its first $a$-block. Since regular languages are closed under intersection,This is the proper-power language is not regular.

Let $K\subseteq \mathbb{N}$ be the undecidable set denoted $\mathbb{K}$ in the question. The language satisfies the pumping lemma for regular languages with pumping length one. For any nonempty $s\in L$, write $s=xyz$ with $x=\epsilon$, $y$ its first symbol, and $z$ the remaining suffix.

If $s\in b^{\ast }$, then $x{y}^{i}z\in b^{\ast }$ for every $i\ge 0$. Otherwise $s=wa{b}^n$ for some $n\in K$. If the chosen first symbol lies in $w$, pumping it preserves the same final suffix $a{b}^n$. If $w=\epsilon$, then $s=a{b}^n$: pumping down gives $b^n\in b^{\ast }$, while every positive pump gives $a^i{b}^n$ and all but its last $a$ can be absorbed into $w$. Thus every sufficiently long word has a valid pumping decomposition.

Nevertheless, if $L$ were regular language, closure under intersection would makeregular. A finite automaton deciding this unary language would decide whether $n\in K$ by running it on $a{b}^n$, contradicting the halting problem. ThereforeThis is a nonregular language satisfying the pumping lemma.

A deterministic finite automaton is a tuple $(Q,\Sigma ,\delta ,q_0,F)$ with finite state set $Q$, finite input alphabet $\Sigma$, transition function $\delta :Q\times \Sigma \to Q$, initial state $q_0$, and accepting-state set $F\subseteq Q$. It accepts a word when the extended transition function of a deterministic finite automaton carries $q_0$ to a state in $F$. A regular language is a language accepted by some deterministic finite automaton.

The pumping lemma for regular languages says that if a regular language is accepted by an automaton with $N$ states, every accepted word $w$ of length at least $N$ has a decomposition $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{i}z$ in the language for every $i\ge 0$. Indeed, among the $N+1$ states visited before and after the first $N$ symbols, two are equal by the pigeonhole principle. The intervening nonempty word $y$ labels a loop, which may be traversed any number of times without changing the final accepting state.

In base two, the powers of two have representations $10^n$, so their language is the regular expression $10^{\ast }$ and is regular.

Suppose instead that their base-ten representations formed a regular language. Apply the pumping lemma to a sufficiently long decimal power of two $xyz$, and put $d=|y|>0$. Pumping gives decimal integers $a_i$ represented by $x{y}^{i}z$, all powers of two. A direct place-value calculation shows thatfor a constant $C$ independent of $i$. The lengths, and hence the exponents in $a_i=2^{n_i}$, tend to infinity. Dividing by $a_i$ givesFor large $i$, the right side has absolute value less than one while the left side is an integer, so it must vanish. This would make a power of two equal to $10^d=2^d{5}^d$, impossible for $d>0$ by unique prime factorization. Thus the decimal powers of two are not a regular language.

The Knaster-Tarski theorem states that the fixed points of a monotone map $f:L\to L$ on a complete lattice form a complete lattice. LetFor every $x\in P$, monotonicity gives $f(m)\le f(x)\le x$, hence $f(m)\le m$. Applying $f$ once more gives $f(f(m))\le f(m)$, so $f(m)\in P$. The definition of $m$ then gives $m\le f(m)$, and therefore $f(m)=m$. Thusis the least fixed point. The order-dual argument shows thatis the greatest fixed point.

More generally, for a family $S$ of fixed points, let $P_S$ be the set of prefixed points $x$ satisfying $f(x)\le x$ and $s\le x$ for every $s\in S$. Its meet $m_S$ is again prefixed. Since $s=f(s)\le f(m_S)$ for every $s\in S$, the element $f(m_S)$ also lies in $P_S$, so the preceding argument gives $f(m_S)=m_S$. It is the join of $S$ within the fixed-point order. The dual construction gives the meet of $S$ within that order, proving completeness.

For the Myhill-Nerode theorem, let $A\subseteq {\Sigma }^{\ast }$ and define the Myhill-Nerode equivalenceThis is an equivalence relation and a right congruence: $u{\sim }_{A}v$ implies $ua{\sim }_{A}va$ for every letter $a$.

If a deterministic finite automaton accepts $A$, any two words reaching the same state are equivalent, because every continuation has the same subsequent run. Hence ${\sim }_A$ has at most as many classes as the automaton has states. Conversely, if ${\sim }_A$ has finitely many classes, define an automaton with state set ${\Sigma }^{\ast }/{\sim }_A$, initial state $[ϵ]$, transitionand accepting states $[u]$ with $u\in A$. Right congruence makes the transition well defined, and induction on word length shows that the state reached by $u$ is $[u]$, so the automaton accepts exactly $A$. Therefore $A$ is a regular language exactly when ${\sim }_A$ has finite index. Moreover, every automaton for $A$ has at least one state for each equivalence class, so this quotient is the minimal deterministic finite automaton.

This language is not regular. If it were regular, its intersection with the regular language $0^{\ast }{1}^{\ast }$ would be regular because regular languages are closed under intersection. That intersection is exactlywhich part (ii) proved nonregular.

Suppose first that $A$ is a regular language, accepted by a deterministic finite automaton $D$. If two words reach the same state, then every continuation is accepted from both or rejected from both. Thus they are equivalent under ${\sim }_A$, and the number of equivalence classes is at most the finite number of states of $D$.

Conversely, suppose ${\sim }_A$ has finitely many classes. Define a deterministic automaton byandThe transition is well defined: if $v{\sim }_{A}w$, then for every suffix $u$,so $va{\sim }_{A}wa$. Likewise, membership in $F$ is independent of the representative by taking the empty suffix in the definition of ${\sim }_A$. Induction givesso the automaton accepts exactly $A$. It has finitely many states, and therefore $A$ is regular. This proves the Myhill-Nerode theorem in the stated formulation. The assumption $\epsilon \notin A$ merely says that the initial state is not accepting.

Given a finite input word $w$, construct the typed term $\mathbf{w}{q}_0$ effectively and beta-normalize it. The Strong normalization theorem for simply typed lambda calculus guarantees termination, and confluence gives exactly one of the finitely many normal forms $q_i$. Compare that normal form syntactically with the listed accepting states in $F$. This algorithm accepts exactly when ${\delta }^{\ast }(q_0,w)\in F$, so $L$ is recursive. Equivalently, this is the standard theorem that every language recognized by a deterministic finite automaton is a regular language and hence decidable.

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 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.

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.