<ol>
<li><p>Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)</p></li>
<li><p>If every iterative/pumping pair of a context-free language L is 
<em>degenerated</em>, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was proved by Ehrenfeucht, Rozenberg, "Strong iterative pairs and the regularity of context-free languages", 1983. See
<a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1990HandbookCfl.pdf">"Context-free languages"</a> by Berstel and Boasson for an exposition.</p></li>
<li><p>If a context-free language is commutative and linear, then it is regular.
(Ehrenfeucht, Haussler, Rozenberg, <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=context%20free%20regularity&amp;source=web&amp;cd=2&amp;ved=0CFMQFjAB&amp;url=http://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-235-82.pdf&amp;ei=s8PIT82pBs3Hsgb2lpH-Dg&amp;usg=AFQjCNHLwMru5mO9cIZD63wx5AAbAzG7xw&amp;cad=rja">"On regularity of Context-free Languages"</a>,  1983)</p></li>
</ol>

CC BY-SA 3.0
2012-06-01T13:53:11.210Z
2012-06-01T13:53:11.210Z
f-h
<p>Let <span class="math-container">$M$</span> be a <a href="https://en.wikipedia.org/wiki/Monoid" rel="nofollow noreferrer">Monoid</a> and, for any subsets <span class="math-container">$A, B ⊆ M$</span> define the left-quotient
<span class="math-container">$$A \backslash B = \{ m ∈ M: (∃a ∈ A) am ∈ B\}.$$</span>
For <span class="math-container">$m ∈ M$</span> and <span class="math-container">$B ⊆ M$</span>, define <span class="math-container">$m \backslash B = \{m\} \backslash B$</span>. The following identities hold:
<span class="math-container">$$
(A ∪ B) \backslash C = (A \backslash C) ∪ (B \backslash C),\quad
(A B) \backslash C = B \backslash (A \backslash C),\quad
1 \backslash A = A,
$$</span>
where <span class="math-container">$A, B, C ⊆ M$</span> and <span class="math-container">$1$</span> denotes the identity of <span class="math-container">$M$</span>.</p>
<p>For the free monoid <span class="math-container">$X^*$</span> generated by a set <span class="math-container">$X$</span>, and for any <span class="math-container">$A ⊆ M$</span>, the set
<span class="math-container">$$Q(A) = \{ w \backslash A: w ∈ X^* \}$$</span>
is the state space for the minimal deterministic automaton corresponding to <span class="math-container">$A$</span>, whose start state is <span class="math-container">$A$</span>, whose state transitions on <span class="math-container">$x ∈ X$</span> from any <span class="math-container">$B ∈ Q(A)$</span> are given by <span class="math-container">$B \overset{x}→ x \backslash B$</span> and whose final states are those <span class="math-container">$B ∈ Q(A)$</span> for which <span class="math-container">$1 ∈ B$</span>.</p>
<p>It resides in a single state diagram that contains the state diagram of every single automaton over <span class="math-container">$X$</span> - both finite and infinite. That, by the way, includes all Turing machines and push-down automata, as well as all oracles for subsets <span class="math-container">$A ⊆ X^*$</span> that lie beyond the Chomsky hierarchy. It is the <strong>Univeral State Diagram</strong> for <span class="math-container">$X^*$</span>.</p>
<p>The set <span class="math-container">$Q(A)$</span> is finite if and only if the minimal deterministic automaton is finite if and only if <span class="math-container">$A$</span> is a regular subset of <span class="math-container">$X^*$</span>.</p>
<p><strong>Example:</strong>
Consider the subset of <span class="math-container">$X^*$</span>, given by the grammar <span class="math-container">$S → u S v$</span>, <span class="math-container">$S → w$</span>, where <span class="math-container">$X = \{u, v, w\}$</span> and denote the subset by <span class="math-container">$S$</span>. Let <span class="math-container">$S(n) = S \{v^n\}$</span> and <span class="math-container">$T(n) = \{v^n\}$</span>, for <span class="math-container">$n = 0, 1, 2, ⋯$</span>. Then,
<span class="math-container">$$Q(S) = \{ S(n): n=0,1,2,⋯ \} ∪ \{ T(n): n=0,1,2,⋯ \} ∪ \{∅\},$$</span>
and the following are its state transitions in the Universal State Diagram for <span class="math-container">$X^*$</span>:
<span class="math-container">$$
S(n) \overset{u}→ S(n+1),\quad S(n) \overset{v}→ ∅,\quad S(n) \overset{w}→ T(n),\\
T(n) \overset{u}→ ∅,\quad T(n+1) \overset{v}→ T(n),\quad T(0) \overset{v}→ ∅,\quad T(n) \overset{w}→ ∅,\\
∅ \overset{u}→ ∅,\quad ∅ \overset{v}→ ∅,\quad ∅ \overset{w}→ ∅.
$$</span>
for <span class="math-container">$n = 0, 1, 2, ⋯$</span>. The start state is <span class="math-container">$S = S(0)$</span> and the sole final state is <span class="math-container">$T(0)$</span></p>
<p>Therefore, <span class="math-container">$S$</span> is not regular.</p>
<p>The state diagram for the minimal deterministic automaton for <span class="math-container">$S$</span> is an infinite ladder with <span class="math-container">$S$</span> and <span class="math-container">$T$</span> rungs, where <span class="math-container">$u$</span> raises the level by one, <span class="math-container">$w$</span> crosses over from the <span class="math-container">$S$</span> rungs to the <span class="math-container">$T$</span> rungs, and <span class="math-container">$v$</span> lowers the level by one, and by convention, the <span class="math-container">$∅$</span> state is not displayed.</p>
<p><strong>Example:</strong> Consider the subset of <span class="math-container">$X^*$</span> given by the grammar <span class="math-container">$S → u S$</span>, <span class="math-container">$S → S v S$</span>, <span class="math-container">$S → S w$</span>, <span class="math-container">$S → x$</span>, where <span class="math-container">$X = \{u, v, w, x\}$</span>. The grammar specifies the subset that is given as the least fixed-point solution to the following
<span class="math-container">$$S ⊇ \{u\} S ∪ S \{v\} S ∪ S \{w\} ∪ \{x\},$$</span>
or algebraically <span class="math-container">$S ≥ u S + S v S + S w + x$</span>, where <span class="math-container">$≥$</span> denotes the subset ordering relation and <span class="math-container">$+$</span> the union operation. The least fixed point solution to <span class="math-container">$y ≥ f(y)$</span> is written as <span class="math-container">$μy·f(y)$</span>.</p>
<p>The one in the previous example could have been written <span class="math-container">$μs·(u s v + w)$</span>.</p>
<p>In <a href="https://en.wikipedia.org/wiki/Kleene_algebra" rel="nofollow noreferrer">Kleene algebra</a>, the least fixed point solution to <span class="math-container">$x ≥ a + x b$</span> is also the least fixed point solution to <span class="math-container">$x ≥ a b^*$</span>, i.e. <span class="math-container">$μx·(a + x b) = μx·(a b^*)$</span>. As such, the grammar for this example could just as well be written in EBNF form as <span class="math-container">$S → (u S | x) (v S | w)^*$</span>, with the corresponding fixed point equation given by <span class="math-container">$S = μs·(u s + x) (v s + w)^*$</span>.</p>
<p>With that having been said, let <span class="math-container">$S$</span> also denote the subset of <span class="math-container">$X^*$</span> recognized by the grammar in this example. The least fixed point solution is also a solution to the corresponding equation, i.e. <span class="math-container">$μx·f(x) = f(μx·f(x))$</span>. Here, that means
<span class="math-container">$$S = (\{u\} S ∪ \{x\}) T,$$</span>
where
<span class="math-container">$$T = (\{v\} S ∪ \{w\})^*,$$</span>
and - since <span class="math-container">$a b^* b^* = a b^*$</span> is a Kleene-algebraic identity - it <em>also</em> means that
<span class="math-container">$$S = S T.$$</span></p>
<p>This is enough to determine that
<span class="math-container">$$Q(S) = \{ S, T, ∅ \},$$</span>
that the state transitions are
<span class="math-container">$$
S \overset{u}→ S,\quad S \overset{v}→ ∅,\quad S \overset{w}→ ∅,\quad S \overset{x}→ T,\\
T \overset{u}→ ∅,\quad T \overset{v}→ S,\quad T \overset{w}→ T,\quad S \overset{x}→ ∅,\\
∅ \overset{u}→ ∅,\quad ∅ \overset{v}→ ∅,\quad ∅ \overset{w}→ ∅,\quad ∅ \overset{x}→ ∅,
$$</span>
that the start state is <span class="math-container">$S$</span>, that the sole final state is <span class="math-container">$T$</span>, that <span class="math-container">$S$</span> is regular and that it is given by the regular expression <span class="math-container">$S = u^* x w^* (v u^* x w^*)^*$</span>. Thus,
<span class="math-container">$$μs·(u s + s v s + s w + x) = u^* x w^* (v u^* x w^*)^*.$$</span></p>
<p>On the other hand, to write the previous example as a regular expression, you would have to add in the following extra symbols <span class="math-container">$Z = \{b,d,p,q\}$</span>, subjecting them to the identities
<span class="math-container">$$
b d = 1 = p q,\quad b q = 0 = p d,\quad z x = x z\quad (x ∈ X,\quad z ∈ Z),
$$</span>
(and, optionally, also to the identity <span class="math-container">$d b + q p = 1$</span>), in which case you may write <span class="math-container">$S = b (u p)^* w (q v)^* d$</span> - i.e. what shall come to be known as a Chomsky-Schützenberger context-free expression, once the new algebraic framework becomes more widely-known.</p>

CC BY-SA 4.0
2024-04-24T19:30:21.047Z
2024-04-24T20:28:44.010Z
2024-04-24T20:28:44.010Z
NinjaDarth
<p>It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form: 
"if a given CFG/PDA has property P, then its languages is regular"</p>

<p>The property P does not have to characterize 
the CFGs generating regular languages. Furthermore, P does not have to be decidable, and P should "somehow depend" on the language being 
context-free ("the syntactic monoid of L is finite", 
"L is decidable in space o(log log n)" and so on, are not what I am looking for).</p>

CC BY-SA 3.0
2012-06-01T00:49:38.413Z
seems very likely the general question is undecidable. the analogy is that there are other theorems that "is B actually A" where A is a "smaller" language class than B is undecidable. I recall a question on here wrt maybe CFLs that was similar but cant find it right now.
vzn
CC BY-SA 3.0
2012-06-01T01:16:08.800Z
by "regularity" you mean, is it really a regular language right?
vzn
CC BY-SA 3.0
2012-06-01T01:21:23.757Z
ok found it. this question is very similar to this one, ["is a CFG actually a RL"](http://cstheory.stackexchange.com/questions/10048/decidability-of-does-this-cfg-define-a-regular-language) & is known to be undecidable
vzn
CC BY-SA 3.0
2012-06-01T08:30:53.983Z
@vzn I think OP is not looking for an algorithm to decide regularity of CFLs but rather for some sufficient conditions. For example, the regularity of a language of a TM is undecidable, but one sufficient condition is that if a language is decidable in $o(n log n)$, then it must be regular.
aelguindy
CC BY-SA 3.0
2012-06-01T15:19:29.180Z
agreed, distinction is valid. but its also critical to know at same time the general problem is undecidable. "sufficient conditions" are generally closely connected with algorithms eg in the example you gave of o(n lg n) time complexity.
vzn
<reference-request><fl.formal-languages><regular-language><context-free><survey>
Sufficient conditions for the regularity of a context-free language
f-h
# Sufficient conditions for the regularity of a context-free language

(Asked by: username_0 on 2012-05-29)

It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"

The property P does not have to characterize
the CFGs generating regular languages. Furthermore, P does not have to be decidable, and P should "somehow depend" on the language being
context-free ("the syntactic monoid of L is finite",
"L is decidable in space o(log log n)" and so on, are not what I am looking for).

**Tags:** reference-request, fl.formal-languages, regular-language, context-free, survey

> **Comments:**
> **username_1**: seems very likely the general question is undecidable. the analogy is that there are other theorems that "is B actually A" where A is a "smaller" language class than B is undecidable. I recall a question on here wrt maybe CFLs that was similar but cant find it right now.  
> **username_1**: by "regularity" you mean, is it really a regular language right?  
> **username_1**: ok found it. this question is very similar to this one, ["is a CFG actually a RL"](http://cstheory.stackexchange.com/questions/10048/decidability-of-does-this-cfg-define-a-regular-language) & is known to be undecidable  
> **username_2**: @username_1 I think OP is not looking for an algorithm to decide regularity of CFLs but rather for some sufficient conditions. For example, the regularity of a language of a TM is undecidable, but one sufficient condition is that if a language is decidable in $o(n log n)$, then it must be regular.  
> **username_1**: agreed, distinction is valid. but its also critical to know at same time the general problem is undecidable. "sufficient conditions" are generally closely connected with algorithms eg in the example you gave of o(n lg n) time complexity.  

---

## 2 answers

### Answer by username_0 on 2012-06-01. Score: 16

1. Every unary context-free language is regular.
   (e.g. a direct consequence of Parikh's theorem)
2. If every iterative/pumping pair of a context-free language L is
   *degenerated*, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
   $$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was proved by Ehrenfeucht, Rozenberg, "Strong iterative pairs and the regularity of context-free languages", 1983. See
   ["Context-free languages"](http://www-igm.univ-mlv.fr/~berstel/Articles/1990HandbookCfl.pdf) by Berstel and Boasson for an exposition.
3. If a context-free language is commutative and linear, then it is regular.
   (Ehrenfeucht, Haussler, Rozenberg, ["On regularity of Context-free Languages"](http://www.google.com/url?sa=t&rct=j&q=context%20free%20regularity&source=web&cd=2&ved=0CFMQFjAB&url=http://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-235-82.pdf&ei=s8PIT82pBs3Hsgb2lpH-Dg&usg=AFQjCNHLwMru5mO9cIZD63wx5AAbAzG7xw&cad=rja), 1983)


---

### Answer by username_3 on 2024-04-24. Score: 0

Let $M$ be a [Monoid](https://en.wikipedia.org/wiki/Monoid) and, for any subsets $A, B ⊆ M$ define the left-quotient
$$A \backslash B = \{ m ∈ M: (∃a ∈ A) am ∈ B\}.$$
For $m ∈ M$ and $B ⊆ M$, define $m \backslash B = \{m\} \backslash B$. The following identities hold:
$$
(A ∪ B) \backslash C = (A \backslash C) ∪ (B \backslash C),\quad
(A B) \backslash C = B \backslash (A \backslash C),\quad
1 \backslash A = A,
$$
where $A, B, C ⊆ M$ and $1$ denotes the identity of $M$.

For the free monoid $X^\*$ generated by a set $X$, and for any $A ⊆ M$, the set
$$Q(A) = \{ w \backslash A: w ∈ X^\* \}$$
is the state space for the minimal deterministic automaton corresponding to $A$, whose start state is $A$, whose state transitions on $x ∈ X$ from any $B ∈ Q(A)$ are given by $B \overset{x}→ x \backslash B$ and whose final states are those $B ∈ Q(A)$ for which $1 ∈ B$.

It resides in a single state diagram that contains the state diagram of every single automaton over $X$ - both finite and infinite. That, by the way, includes all Turing machines and push-down automata, as well as all oracles for subsets $A ⊆ X^\*$ that lie beyond the Chomsky hierarchy. It is the **Univeral State Diagram** for $X^\*$.

The set $Q(A)$ is finite if and only if the minimal deterministic automaton is finite if and only if $A$ is a regular subset of $X^\*$.

**Example:**
Consider the subset of $X^\*$, given by the grammar $S → u S v$, $S → w$, where $X = \{u, v, w\}$ and denote the subset by $S$. Let $S(n) = S \{v^n\}$ and $T(n) = \{v^n\}$, for $n = 0, 1, 2, ⋯$. Then,
$$Q(S) = \{ S(n): n=0,1,2,⋯ \} ∪ \{ T(n): n=0,1,2,⋯ \} ∪ \{∅\},$$
and the following are its state transitions in the Universal State Diagram for $X^\*$:
$$
S(n) \overset{u}→ S(n+1),\quad S(n) \overset{v}→ ∅,\quad S(n) \overset{w}→ T(n),\\
T(n) \overset{u}→ ∅,\quad T(n+1) \overset{v}→ T(n),\quad T(0) \overset{v}→ ∅,\quad T(n) \overset{w}→ ∅,\\
∅ \overset{u}→ ∅,\quad ∅ \overset{v}→ ∅,\quad ∅ \overset{w}→ ∅.
$$
for $n = 0, 1, 2, ⋯$. The start state is $S = S(0)$ and the sole final state is $T(0)$

Therefore, $S$ is not regular.

The state diagram for the minimal deterministic automaton for $S$ is an infinite ladder with $S$ and $T$ rungs, where $u$ raises the level by one, $w$ crosses over from the $S$ rungs to the $T$ rungs, and $v$ lowers the level by one, and by convention, the $∅$ state is not displayed.

**Example:** Consider the subset of $X^\*$ given by the grammar $S → u S$, $S → S v S$, $S → S w$, $S → x$, where $X = \{u, v, w, x\}$. The grammar specifies the subset that is given as the least fixed-point solution to the following
$$S ⊇ \{u\} S ∪ S \{v\} S ∪ S \{w\} ∪ \{x\},$$
or algebraically $S ≥ u S + S v S + S w + x$, where $≥$ denotes the subset ordering relation and $+$ the union operation. The least fixed point solution to $y ≥ f(y)$ is written as $μy·f(y)$.

The one in the previous example could have been written $μs·(u s v + w)$.

In [Kleene algebra](https://en.wikipedia.org/wiki/Kleene_algebra), the least fixed point solution to $x ≥ a + x b$ is also the least fixed point solution to $x ≥ a b^\*$, i.e. $μx·(a + x b) = μx·(a b^\*)$. As such, the grammar for this example could just as well be written in EBNF form as $S → (u S | x) (v S | w)^\*$, with the corresponding fixed point equation given by $S = μs·(u s + x) (v s + w)^\*$.

With that having been said, let $S$ also denote the subset of $X^\*$ recognized by the grammar in this example. The least fixed point solution is also a solution to the corresponding equation, i.e. $μx·f(x) = f(μx·f(x))$. Here, that means
$$S = (\{u\} S ∪ \{x\}) T,$$
where
$$T = (\{v\} S ∪ \{w\})^\*,$$
and - since $a b^\* b^\* = a b^\*$ is a Kleene-algebraic identity - it *also* means that
$$S = S T.$$

This is enough to determine that
$$Q(S) = \{ S, T, ∅ \},$$
that the state transitions are
$$
S \overset{u}→ S,\quad S \overset{v}→ ∅,\quad S \overset{w}→ ∅,\quad S \overset{x}→ T,\\
T \overset{u}→ ∅,\quad T \overset{v}→ S,\quad T \overset{w}→ T,\quad S \overset{x}→ ∅,\\
∅ \overset{u}→ ∅,\quad ∅ \overset{v}→ ∅,\quad ∅ \overset{w}→ ∅,\quad ∅ \overset{x}→ ∅,
$$
that the start state is $S$, that the sole final state is $T$, that $S$ is regular and that it is given by the regular expression $S = u^\* x w^\* (v u^\* x w^\*)^\*$. Thus,
$$μs·(u s + s v s + s w + x) = u^\* x w^\* (v u^\* x w^\*)^\*.$$

On the other hand, to write the previous example as a regular expression, you would have to add in the following extra symbols $Z = \{b,d,p,q\}$, subjecting them to the identities
$$
b d = 1 = p q,\quad b q = 0 = p d,\quad z x = x z\quad (x ∈ X,\quad z ∈ Z),
$$
(and, optionally, also to the identity $d b + q p = 1$), in which case you may write $S = b (u p)^\* w (q v)^\* d$ - i.e. what shall come to be known as a Chomsky-Schützenberger context-free expression, once the new algebraic framework becomes more widely-known.


---

