DesCo

Name	Description	Subset of
All-sided Ideal	A non-empty language $L \subseteq \Sigma^$ is a all-sided ideal* if $L = \Sigma^*\shuffle L$; the complement is subword converse-closed. More
Bifix-closed	If a language is both prefix-closed and suffix-closed then it is also bifix-closed. This language is: Prefix-closed $\cap$ Suffix-closed More
Bifix-convex	If a language is both prefix-convex and suffix-convex then it is also bifix-convex. This language is: Prefix-convex $\cap$ Suffix-convex More
Bifix-free	A language is bifix-free if it is both prefix-free and suffix-free. Bifix-free languages are subsets of prefix-free, suffix-free, bifix-convex. Bifix-free languages other than $\{\epsilon\}$ are bifix codes. More
Factor-closed	If $u$, $v$, $w$, $x \in \Sigma^$ and $w=uxv$ then $x$ is a factor of $w$. A language $L$ is factor-closed* if, whenever $w \in L$ and $v$ is a factor of $w$, then $v \in L$. More
Factor-convex	If $u$, $v$, $w$, $x \in \Sigma^$ and $w=uxv$ then $x$ is a factor of $w$. A language $L$ is factor-convex* if $u$, $v$, $w \in \Sigma^*$, $u$ is a factor of $v$ and $v$ is factor of $w$ with $u$, $w \in L$, then $v \in L$. More
Factor-free	If $u,v,w,x\in\Sigma^$ and $w=uxv$ then $x$ is a factor* of $w$. A factor of $w$ is also called an infix of $w$. A language $L$ is factor-free if, whenever $ w\in L$ and $v$ is a factor of $w$, then $v$ is not in $L$. Factor-free languages are subsets of bifix-free and factor-convex. Factor-free languages other than $\{\epsilon\}$ are infix codes. More
Factor-free regular	This language is: Factor-free $\cap$ Regular More
Finite	Finite languages are an important subset of regular languages. They are accepted by complete DFAs that are acyclic apart from a loop on the sink state for all alphabetic symbols. More
Left Ideal	A non-empty language $L \subseteq \Sigma^$ is a left* ideal if $L = \Sigma^*L$; the complement is suffix converse-closed. More
Prefix-closed	If $u,v,w\in\Sigma^$ and $w=uv$, then $u$ is a prefix* of $w$. A language $L$ is prefix-closed if, whenever $w\in L$ and $v$ is a prefix of $w$, then $v$ is also in $L$. Every prefix-closed language is the complement of a right ideal. More
Prefix-closed regular	This language is: Prefix-closed $\cap$ Regular More
Prefix-convex	If $u,v,w \in \Sigma^\star$ and $w = uv$ then $u$ is prefix of $w$. A language $L$ is prefix-convex if $\forall_{ u,v,w }$ $u$ is prefix of $v$ and $v$ is prefix of $w$ with $u,w \in L$ implies $v \in L$. More
Prefix-free	If $u,v,w \in \Sigma^\star$ and $w = uv$ then, $u$ is prefix of $w$. A language $L$ is a prefix-free if, whenever $w \in L$ and $v$ is a prefix of $w$ then $v \notin L$. Prefix-free languages are subsets of prefix-convex languages. Prefix-free languages other than $\{\epsilon\}$ are prefix codes. More
Prefix-free regular	This language is: Prefix-free $\cap$ Regular More
Regular	The set of regular languages over an alphabet $\Sigma$ can be defined recursively as follows: The empty language $\emptyset$ is regular The empty word language $\{\epsilon \}$ is regular For each $a \in \Sigma$, the language $\{ a \}$ is regular If $A$ and $B$ are both regular languages, then $A\cup B$ (union), $AB$ (concatenation), and $A^\star$ (Kleene star) are regular languages No other languages over $\Sigma$ are regular To prove that a language is regular, one can define a DFA, NFA, regular expression, etc. that recognizes that language. To prove that a language is not regular, a pumping lemma can be used. More
Right Ideal	A non-empty language $L \subseteq \Sigma^$ is a right ideal* if $L = L\Sigma^*$; the complement is prefix converse-closed. More
Star-free	Star-free languages are the languages constructed from finite languages using only boolean operations and concatenation. More
Subword-closed	If $w=u_0 v_1 u_1 ... v_n u_n$ where $u_i$, $v_i \in \Sigma^$, then $v=v_1 v_2 ... v_n$ is a subword of $w$. A language $L$ is subword-closed* if, whenever $w \in L$ and $v$ is a subword of $w$, then $v \in L$. More
Subword-convex	If $w=u_0 v_1 u_1 ... v_n u_n$, where $u_i$ ,$v_i\in\Sigma^$, then $v=v_1 v_2 ... v_n$ is a subword of $w$. A language $L$ is subword-convex* if $u$, $v$, $w \in \Sigma^*$, $u$ is a subword of $v$ and $v$ is subword of $w$ with $u$, $w \in L$, then $v \in L$. More
Subword-free	If $w=u_0v_1u_1\cdots v_nu_n$, where $u_i,v_i\in\Sigma^$, then $v=v_1v_2\cdots v_n$ is a subword* of $w$. It is also known as scattered subword or subsequence. A language $L$ is subword-free if, whenever $w\in L$ and $v$ s a subword of $w$, then $v$ is not in $L$. Subword-free languages are subsets of factor-free and subword-convex. Every subword-free language is finite. Subword-free languages other than $\{\epsilon\}$ are hypercodes More
Suffix-closed	If $u$, $v$, $w \in \Sigma^*$ and $w=uv$ then $v$ is a suffix of $w$. A language $L$ is suffix-closed if, whenever $w \in L$ and $v$ is a suffix of $w$, then $v \in L$. More
Suffix-convex	If $u,v,w \in \Sigma^\star$ and $w = uv$, then $v$ is suffix of $w$. A language $L$ is suffix-convex if $u,v,w \in \Sigma^\star$, $u$ is suffix of $v$ and $v$ is suffix of $w$ with $u,w \in L$ implies $v \in L$. More
Suffix-free	If $u,v,w \in \Sigma^\star$ and $w = uv$ then $v$ is suffix of $w$. A language $L$ is suffix-free if, whenever if $ w\in L$ and $v$ is a suffix of $w$ then $v \notin L$. Suffix-free languages are subsets of suffix-convex languages. Suffix-free languages other than $\{\epsilon\}$ are suffix codes. More
Suffix-free regular	This language is: Suffix-free $\cap$ Regular More
Two-sided Ideal	A non-empty language $L \subseteq \Sigma^$ is a two-sided ideal* if $L = \Sigma^L\Sigma^$; the complement is bifix converse-closed. More

All-sided Ideal

A non-empty language $L \subseteq \Sigma^*$ is a all-sided ideal if $L = \Sigma^*\shuffle L$; the complement is subword converse-closed. More

Bifix-closed

If a language is both prefix-closed and suffix-closed then it is also bifix-closed.

This language is: Prefix-closed $\cap$ Suffix-closed

More

Bifix-convex

If a language is both prefix-convex and suffix-convex then it is also bifix-convex.

This language is: Prefix-convex $\cap$ Suffix-convex

More

Bifix-free

A language is bifix-free if it is both prefix-free and suffix-free.
Bifix-free languages are subsets of prefix-free, suffix-free, bifix-convex.
Bifix-free languages other than $\{\epsilon\}$ are bifix codes.

More

Factor-closed

If $u$, $v$, $w$, $x \in \Sigma^*$ and $w=uxv$ then $x$ is a factor of $w$.
A language $L$ is factor-closed if, whenever $w \in L$ and $v$ is a factor of $w$, then $v \in L$.

More

Factor-convex

If $u$, $v$, $w$, $x \in \Sigma^*$ and $w=uxv$ then $x$ is a factor of $w$.

A language $L$ is factor-convex if $u$, $v$, $w \in \Sigma^*$, $u$ is a factor of $v$ and $v$ is factor of $w$ with $u$, $w \in L$, then $v \in L$.

More

Factor-free

If $u,v,w,x\in\Sigma^*$ and $w=uxv$ then $x$ is a factor of $w$.
A factor of $w$ is also called an infix of $w$.
A language $L$ is factor-free if, whenever $ w\in L$ and $v$ is a factor of $w$, then $v$ is not in $L$.
Factor-free languages are subsets of bifix-free and factor-convex.
Factor-free languages other than $\{\epsilon\}$ are infix codes.

More

Factor-free regular

This language is: Factor-free $\cap$ Regular

More

Finite

Finite languages are an important subset of regular languages. They are accepted by complete DFAs that are acyclic apart from a loop on the sink state for all alphabetic symbols.

More

Left Ideal

A non-empty language $L \subseteq \Sigma^*$ is a left ideal if $L = \Sigma^*L$; the complement is suffix converse-closed. More

Prefix-closed

If $u,v,w\in\Sigma^*$ and $w=uv$, then $u$ is a prefix of $w$.
A language $L$ is prefix-closed if, whenever $w\in L$ and $v$ is a prefix of $w$, then $v$ is also in $L$.
Every prefix-closed language is the complement of a right ideal.

More

Prefix-closed regular

This language is: Prefix-closed $\cap$ Regular

More

Prefix-convex

If $u,v,w \in \Sigma^\star$ and $w = uv$ then $u$ is prefix of $w$.

A language $L$ is prefix-convex if $\forall_{ u,v,w }$ $u$ is prefix of $v$ and $v$ is prefix of $w$ with $u,w \in L$ implies $v \in L$.

More

Prefix-free

If $u,v,w \in \Sigma^\star$ and $w = uv$ then, $u$ is prefix of $w$.
A language $L$ is a prefix-free if, whenever $w \in L$ and $v$ is a prefix of $w$ then $v \notin L$.
Prefix-free languages are subsets of prefix-convex languages.
Prefix-free languages other than $\{\epsilon\}$ are prefix codes.

More

Prefix-free regular

This language is: Prefix-free $\cap$ Regular

More

Regular

The set of regular languages over an alphabet $\Sigma$ can be defined recursively as follows:

The empty language $\emptyset$ is regular
The empty word language $\{\epsilon \}$ is regular
For each $a \in \Sigma$, the language $\{ a \}$ is regular
If $A$ and $B$ are both regular languages, then $A\cup B$ (union), $AB$ (concatenation), and $A^\star$ (Kleene star) are regular languages
No other languages over $\Sigma$ are regular

To prove that a language is regular, one can define a DFA, NFA, regular expression, etc. that recognizes that language.
To prove that a language is not regular, a pumping lemma can be used.

More

Right Ideal

A non-empty language $L \subseteq \Sigma^*$ is a right ideal if $L = L\Sigma^*$; the complement is prefix converse-closed. More

Star-free

Star-free languages are the languages constructed from finite languages using only boolean operations and concatenation.

More

Subword-closed

If $w=u_0 v_1 u_1 ... v_n u_n$ where $u_i$, $v_i \in \Sigma^*$, then $v=v_1 v_2 ... v_n$ is a subword of $w$.
A language $L$ is subword-closed if, whenever $w \in L$ and $v$ is a subword of $w$, then $v \in L$.

More

Subword-convex

If $w=u_0 v_1 u_1 ... v_n u_n$, where $u_i$ ,$v_i\in\Sigma^*$, then $v=v_1 v_2 ... v_n$ is a subword of $w$.

A language $L$ is subword-convex if $u$, $v$, $w \in \Sigma^*$, $u$ is a subword of $v$ and $v$ is subword of $w$ with $u$, $w \in L$, then $v \in L$.

More

Subword-free

If $w=u_0v_1u_1\cdots v_nu_n$, where $u_i,v_i\in\Sigma^*$, then $v=v_1v_2\cdots v_n$ is a subword of $w$. It is also known as scattered subword or subsequence.
A language $L$ is subword-free if, whenever $w\in L$ and $v$ s a subword of $w$, then $v$ is not in $L$.
Subword-free languages are subsets of factor-free and subword-convex.
Every subword-free language is finite.
Subword-free languages other than $\{\epsilon\}$ are hypercodes

More

Suffix-closed

If $u$, $v$, $w \in \Sigma^*$ and $w=uv$ then $v$ is a suffix of $w$.
A language $L$ is suffix-closed if, whenever $w \in L$ and $v$ is a suffix of $w$, then $v \in L$.

More

Suffix-convex

If $u,v,w \in \Sigma^\star$ and $w = uv$, then $v$ is suffix of $w$.

A language $L$ is suffix-convex if $u,v,w \in \Sigma^\star$, $u$ is suffix of $v$ and $v$ is suffix of $w$ with $u,w \in L$ implies $v \in L$.

More

Suffix-free

If $u,v,w \in \Sigma^\star$ and $w = uv$ then $v$ is suffix of $w$.
A language $L$ is suffix-free if, whenever if $ w\in L$ and $v$ is a suffix of $w$ then $v \notin L$.
Suffix-free languages are subsets of suffix-convex languages.
Suffix-free languages other than $\{\epsilon\}$ are suffix codes.

More

Suffix-free regular

This language is: Suffix-free $\cap$ Regular

More

Two-sided Ideal

A non-empty language $L \subseteq \Sigma^*$ is a two-sided ideal if $L = \Sigma^*L\Sigma^*$; the complement is bifix converse-closed. More