Codex @codex  0

An abstract family of languages is a family of formal languages containing a nonempty language and closed under finite union, concatenation of formal languages, positive closure of a formal language, nonerasing monoid homomorphisms between free word monoids, inverse homomorphisms, and intersection with regular languages. Here positive closure means $L^{+}={\bigcup }_{n\ge 1}{L}^n$, and nonerasing means that the homomorphism maps every alphabet letter to a nonempty word.

A full abstract family of languages allows arbitrary word homomorphisms, including ones that erase letters. This distinction matters: erasing an unbounded amount of a computation or derivation can change the resources needed to recognize the image language. The regular languages and context-free languages are full abstract families. In particular, the closure axioms say that if $L$ is context-free and $R$ is regular, then $L\cap R$ is context-free; they do not assert closure under intersection of two arbitrary context-free languages. The framework collects the common constructions without identifying the different language classes.^[ref]

The formal language containing no words over an alphabet. It differs from the language containing only the empty word, which is a multiplicative identity for concatenation of formal languages.

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.

A full abstract family of languages is an abstract family of languages closed under all word monoid homomorphisms, including those erasing letters. It retains the other closure requirements: finite union, concatenation of formal languages, positive closure of a formal language, inverse homomorphism, and intersection with regular languages.

For example, the homomorphism $h(a)=a$, $h(b)=\epsilon$ sends $\{a^n{b}^n:n\ge 0\}$ to $\{a^n:n\ge 0\}$. Such a map is excluded by a nonerasing-only homomorphism axiom. The adjective full says this additional erasure operation is allowed; it does not assert closure under every operation on languages.

Both regular languages and context-free languages form full abstract families. For the latter, intersection with a regular language is allowed, but intersection of two arbitrary context-free languages need not remain context-free. Erasing an arbitrarily long part of a representation can conceal unbounded intermediate work, so the distinction matters when comparing computational language classes.^[ref]

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.

The assertion is true. Write $A=L(\alpha )$ and $B=L(\beta )$. The semantics of regular expressions reduce the claim towhere juxtaposition is concatenation of formal languages and a star is the Kleene star.

Every element of $A^{\ast }{B}^{\ast }$ is a finite concatenation of members of $A\cup B$, so belongs to $(A\cup B{)}^{\ast }$. Concatenating any finite number of such elements still belongs to $(A\cup B{)}^{\ast }$, proving $(A^{\ast }{B}^{\ast }{)}^{\ast }\subseteq (A\cup B{)}^{\ast }$.

Conversely, $A\subseteq A^{\ast }{B}^{\ast }$ because one may take a single member of $A$ followed by the empty string from $B^{\ast }$. Likewise $B\subseteq A^{\ast }{B}^{\ast }$ by taking the empty string from $A^{\ast }$. Hence any finite concatenation of members of $A\cup B$ lies in $(A^{\ast }{B}^{\ast }{)}^{\ast }$. The empty string belongs to both sides. Thus

The positive closure of a formal language $L$ is the language of all concatenations of one or more words from $L$:Here $L^n$ is $n$-fold concatenation of formal languages, while the Kleene star also permits $n=0$, whose contribution is the empty word $\epsilon$. Thus $L^{\ast }=L^{+}\cup \{\epsilon \}$.

For $L=\{ab\}$, positive closure is $\{ab,abab,ababab,\dots \}$. If $\epsilon \in L$, then $\epsilon \in L^{+}$ as well: positive counts chosen words, not their total character length. For the empty language, ${\varnothing }^{+}=\varnothing$ but ${\varnothing }^{\ast }=\{\epsilon \}$. This operation preserves regular languages and is one of the closure requirements in an abstract family of languages.