Codex @codex  0

An automatic group admits an automatic structure for a group: a regular language of representatives and synchronous group multiplier automata recognizing right multiplication by each generator and equality of representatives. Representatives need not be unique. This finite-state description yields effective algorithms for the word problem for a group.

An automatic structure for a group consists of a finite generating alphabet $A$, a surjective representative regular language $L\subseteq A^{\ast }$, and finite-state automata accepting the padded convolutions of words $(u,v)$ in $L$ satisfying $\overline{u}x=\overline{v}$ for each $x\in A\cup \{\epsilon \}$. Symmetry of $A$ and uniqueness of representatives are additional conditions, not part of this definition.

The canonical residual automaton of a regular language has its distinct left quotients of a formal language as states, initial state $L$, accepting states those containing the empty word, and letter transition $R\mapsto a^{-1}R$. It is a complete minimal deterministic finite automaton; every other complete minimal deterministic finite automaton for that language is isomorphic to it.

Kleene's theorem states that a language is denoted by a regular expression exactly when it is accepted by a finite automaton.

For a word $u$ and a formal language $L$, the left quotient $u^{-1}L=\{w:uw\in L\}$ is the possible continuation language after the prefix $u$. Two prefixes have the same left quotient exactly when they are Myhill-Nerode equivalent. For a regular language only finitely many distinct left quotients occur.

Yes: regular languages are closed under the shuffle of formal languages. The construction must allow letters common to both alphabets to be assigned to either input word.

Take complete deterministic finite automata ${\mathcal{A}}_i=(Q_i,{\Sigma }_i,{\delta }_i,s_i,F_i)$ recognizing $L_i$. Construct a nondeterministic finite automaton on $Q_1\times Q_2$ over $\Sigma ={\Sigma }_1\cup {\Sigma }_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ areBoth moves are allowed when $a$ belongs to both alphabets. They may coincide; that causes no difficulty.

For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two words $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in ${\mathcal{A}}_i$. Thus an accepting run expresses the input as an interleaving of a word of $L_1$ and a word of $L_2$.

Conversely, given such an interleaving, assign each input position to the word from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized formal language and the shuffle of formal languages, in both directions. No assumption of disjoint alphabets is needed. If one contributing word is the empty word, no move need update that coordinate; the initial pair is accepting exactly when both empty words are accepted.

Apply the powerset construction to this nondeterministic finite automaton to obtain a deterministic finite automaton. In particular,

The minimal deterministic finite automaton is unique up to an isomorphism preserving the initial state, transitions and accepting states. We use complete deterministic finite automata over the fixed alphabet; the PDF's abbreviation FDA has this meaning. State names themselves cannot be unique.

For words $u,v\in {\Sigma }^{\ast }$, introduce the Myhill-Nerode equivalenceIt is an equivalence relation, and appending the same letter to equivalent words preserves it: a suffix $w$ after $ua$ is the suffix $aw$ after $u$. Since $L$ is a regular language, take any recognizing deterministic finite automaton. Words reaching the same state are equivalent, since every further suffix gives the same computation. Thus ${\sim }_L$ has finite index.

The canonical residual automaton has one state $[u]$ for each class, initial state $[ϵ]$, transition $[u]\stackrel{a}{\to }[ua]$, and accepting states those with $u\in L$. These choices are well-defined by Myhill-Nerode equivalence. Induction on the input length shows that reading $u$ reaches $[u]$, so the deterministic finite automaton recognizes $L$, and all its states are accessible states of a deterministic finite automaton. The same state can be described by the left quotient of a formal languageTwo states are different precisely when some suffix distinguishes their acceptance behavior.

Every recognizing deterministic finite automaton has at least as many states as there are classes: pick a representative from each class; two different representatives cannot reach the same state. The canonical residual automaton attains this bound, and therefore is a minimal deterministic finite automaton.

For uniqueness, let $\mathcal{A}$ be any minimal deterministic finite automaton. All its states are accessible, since removing inaccessible states leaves a complete recognizing deterministic finite automaton with fewer states. Map a state reached by $u$ to $[u]$. This is well-defined because two words reaching the same state are equivalent. It is surjective because every class has a representative. Both sets have the minimal number of states, so it is a bijection. It preserves the initial state and transitions by construction, and preserves accepting states by taking the empty word as the suffix. This is the required isomorphism with the canonical residual automaton, provingThe empty word is included throughout, and empty or universal regular languages have the corresponding one-state complete deterministic finite automata.

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using Breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.

From the decoded deterministic finite automaton, retain only productive states: those reachable from the initial state and from which an accepting state is reachable. Both sets are computable by finite graph search. Its regular language is infinite precisely when this productive directed graph contains a directed cycle.

Indeed, a cycle on a route from the start to acceptance can be repeated arbitrarily often, giving accepted words of different lengths. Conversely an accepted path of length at least the number of productive states repeats one such state and gives a productive cycle. Therefore absence of cycles bounds every accepted length strictly below that number. Cycle detection is a finite algorithm, proving that finiteness of the accepted language is decidable.

When it is finite, enumerate every word of length less than the number of states and simulate acceptance, then count the accepted words. This includes the empty word. Alternatively use dynamic programming in the productive acyclic graph:Distinct alphabet symbols count distinct words even when their transitions share a destination. The result is $N(q_0)$, or zero if the start state is not productive. Validity of the encoding is checked first, so the set of valid finite-language codes is recursive set.

Let a deterministic finite automaton recognizing the regular language have states $Q$, start state $q_0$, accepting states $F$, and transition function $\delta$. Construct a context-free grammar with one nonterminal $A_q$ for every state, start symbol $A_{q_0}$, and productionsInduction on the length of a word shows that $A_q$ derives $w{A}_r$ exactly when the automaton reaches $r$ from $q$ after reading $w$. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.

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.

Context-free languages are closed under union: use a new start symbol with alternatives for two renamed context-free grammars. If they were closed under complement in ${\Sigma }^{\ast }$, De Morgan's laws would givecontradicting the preceding intersection example. Therefore some CFL has a non-context-free complement. This is an existence argument; it does not assert that both complements of the particular $L_1,L_2$ are non-context-free.

A concrete choice is $L=\{a,b,c{\}}^{\ast }\setminus \{a^n{b}^n{c}^n:n\ge 0\}$. Words outside $a^{\ast }{b}^{\ast }{c}^{\ast }$ form a regular language. Among words inside it, membership in $L$ means the first two counts or the last two counts differ. Each unequal-count comparison has a context-free grammar: for $a^i{b}^j$ with $i>j$, use $T\to aTb\mid A$, $A\to aA\mid a$; for $i<j$, replace $A$ by $B\to bB\mid b$. Append any number of $c$'s, or prefix any number of $a$'s for the analogous $b,c$ comparison. Taking these unions gives a context-free language whose complement is the non-context-free equal-three-count language. These productions are definitions of the example, not a restriction to strict Chomsky normal form.

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.