Codex @codex  0

No: regular languages are not closed under countably infinite intersection. Let $\Sigma =\{0,1\}$ and putThe first term in $L_i$ has regular expression $(0\cup 1{)}^i(0\cup 1{)}^{\ast }$, where the fixed power $i$ means $i$ copies. The second term is a finite language, a finite union of single words. Their union is therefore a regular language.

If $w\in K$, then for each $i$ either $|w|\ge i$ or $w$ belongs to the second term, so $w\in L_i$. If $w\notin K$, choose $i>|w|$. It belongs to neither term of $L_i$. ConsequentlyThe formal language $K$ is not a regular language. Indeed, for a proposed pumping length $p\ge 1$, the pumping lemma for regular languages applied to $0^p{1}^p$ must pump a nonempty block consisting only of zeros. Repeating that block increases the number of zeros without increasing the number of ones, leaving $K$. This contradiction proves the counterexample. Finite intersection closure does not extend to this infinite intersection of regular languages.

Every generated word satisfieswhere ${\#}_a,{\#}_b$ count occurrences of the indicated terminal symbols. To see this, follow the unique chain of $S$ occurrences in a parse tree. Each use of $S\to UST$ introduces one $a$ from $U$, at least one $b$ from its rightmost $T$, and possibly one further $b$ from $U\to aT$. Each use of $S\to ST$ adds one $b$ and no $a$. The terminating $S\to \epsilon$ contributes neither. Hence no generated word has more $a$ symbols than $b$ symbols.

Also, for every $n\ge 0$, the word $a^n{b}^n$ is generated: apply $S\to UST$ exactly $n$ times, choose $U\to a$ each time, then use $S\to \epsilon$ and all remaining $T\to b$.

Suppose $L(G)$ were a regular language, and let $p\ge 1$ be a pumping length from the pumping lemma for regular languages. Apply it to $w=a^p{b}^p$. Every allowed decomposition $w=xyz$ with $|xy|\le p$ and $|y|>0$ has $y=a^r$ for some $r\ge 1$. Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore $L(G)$ is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.

Treat the fixed letters $a_1,\dots ,a_n$, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.

If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then $a_1$, then some closing parentheses would be regular. That intersection is exactlyThe pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.

Use $L=\{a^n{b}^n:n\ge 0\}$. The context-free grammar $S\to aSb\mid \epsilon$ generates exactly $L$, so it is a context-free language. It is not a regular language: if $p$ is a pumping length, any allowed decomposition of $a^p{b}^p$ has a nonempty pumped segment consisting only of $a$'s. Pumping down leaves fewer $a$'s than $b$'s, contradicting the pumping lemma for regular languages. Thus $L$ is a context-free language but not a regular language.

Let $K$ be the diagonal halting set, which is undecidable. The pumping argument below actually holds for every subset $K\subseteq \mathbb{N}$; nonregularity needs the stated convention, or at least a set of exponents whose unary language is nonregular.

The pumping lemma for regular languages holds with pumping length one. For an accepted nonempty word, pump its first symbol. A word containing only $1$s remains in $1^{\ast }$ even if that symbol is deleted. If there is a zero and a nonempty prefix before its last zero, pumping the first symbol leaves the last zero and its following $n\in K$ ones unchanged. If the word is $01^n$, pumping its initial zero produces $0^i{1}^n$; this is accepted for $i\ge 1$, and for $i=0$ it belongs to $1^{\ast }$. In every case the pumped substring is nonempty and lies in the first position.

If $L$ were a regular language, closure under intersection would makeregular. A finite-state automaton for this intersection would decide membership of $n$ in the diagonal halting set by reading $01^n$, a contradiction. Thus $L$ satisfies the pumping lemma but is not regular, under the usual meaning of $\mathbb{K}$. If $K$ were arbitrary, the printed conclusion would be false, for example for $K=\mathbb{N}$.

The pumping lemma for regular languages states that for every regular language $L$ there is an integer $N$ such that every $w\in L$ with $|w|\ge N$ can be writtenwith

To prove it, let a deterministic finite automaton with $N$ states recognize $L$. During the reading of the first $N$ symbols of an accepted word $w$, the automaton visits $N+1$ states, including the initial state. By the pigeonhole principle, two of them agree, say $q_i=q_j$ with $0\le i<j\le N$. Let $x$ be the first $i$ symbols, $y$ the next $j-i$ symbols, and $z$ the remaining suffix. Reading $y$ is a nonempty closed path from $q_i$ to itself. Traversing this path any number $r\ge 0$ of times and then reading $z$ therefore reaches the same accept state. This proves all three assertions.

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 pumping lemma for regular languages says that sufficiently long accepted words split as $xyz$ with $|xy|\le P$, $|y|>0$, and $x{y}^{k}z$ accepted for all $k\ge 0$. Applying it to $0^P{1}^{P}01$ pumps only zeros, so language (i) is not regular.

The pumping lemma for regular languages states that if $L$ is regular, then some $p\ge 1$ has the following property: every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for every $i\ge 0$. Indeed, while a deterministic finite automaton with $p$ states reads the first $p$ symbols, two of the first $p+1$ visited states coincide; the intervening nonempty loop may be traversed any number of times.

The language $\{0^{n^2}1:n\ge 0\}$ is not regular. If its pumping length were $p$, apply the lemma to $w=0^{p^2}1$. The pumped block is $y=0^r$ for some $1\le r\le p$. Pumping once more gives $p^2+r$ zeros, butso their number is not a square.

Let $N=|Q|$. The pumping lemma for regular languages states that every $w\in L(D)$ with $|w|\ge N$ can be writtenwithThus one may take the pumping number to be exactly the number $N$ of states of the given automaton, whether or not all of them are accessible.

The pumping lemma for regular languages says that for some $N$, every accepted word $w$ of length at least $N$ factors $w=xyz$ with $|xy|\le N$, $|y|>0$, and $x{y}^{k}z$ accepted for every $k\ge 0$.

The assertion is false. Use the pumping lemma for regular languages: if $L$ is a regular language, there is $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ admits a factorization $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{k}z\in L$ for every integer $k\ge 0$.

Suppose the stated formal language were a regular language, and take $w=0^{2p}{1}^p$. This string has twice as many zeros as ones, so it belongs to $L$. In every allowed factorization, the first $p$ positions are all zeros, forcing $y=0^d$ with $1\le d\le p$. Pumping down with $k=0$ producesIt still has $p$ ones but fewer than $2p$ zeros, contradicting the pumping lemma for regular languages. Thus

The assertion is false. Suppose the formal language $L=\{ww:w\in \{0,1{\}}^{\ast }\}$ were a regular language, and let $p$ be its constant from the pumping lemma for regular languages. ConsiderIn every decomposition $t=xyz$ with $|xy|\le p$ and $|y|\ge 1$, the pumped factor is $y=0^d$ with $1\le d\le p$. Pumping down givesThis string has exactly two ones and ends in a one. If it were $vv$, each copy of $v$ would contain exactly one one, and each copy would end in a one. The first copy would consequently be $0^{p-d}1$, while the second would be $0^{p}1$. They have different lengths because $d>0$, so they cannot be equal. This contradiction to the pumping lemma for regular languages proves

These strings are the even-length palindromes $u{u}^R$. Suppose this were a regular language, and let $p$ be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with $u=0^{p}1$. In any allowed decomposition $w=abc$, where $|ab|\le p$ and $|b|>0$, the pumped block is $b=0^k$ with $1\le k\le p$. Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form $u{u}^R$, contradicting the pumping lemma for regular languages. Therefore

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.

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.