<p>Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.</p>

<p>Regarding DCFL, I have two references (from Hopcroft+Ullman 79):</p>

<ul>
<li><p><a href="http://www.sciencedirect.com/science/article/pii/S0019995867905918">A regularity test for pushdown machines</a>,  R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)</p></li>
<li><p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.8903&amp;rep=rep1&amp;type=pdf">Regularity and Related Problems for Deterministic Pushdown Automata</a>, Leslie G. Valiant, JACM 1975</p></li>
</ul>

<p>Regarding a procedure to get a regular version when possible, I have no suggestion.</p>

CC BY-SA 3.0
2015-03-14T15:54:09.997Z
The procedure to get a regular grammar can't exist. Given a Turing machine $M$ one can construct a Context-free grammar whose language is either $\Sigma^{*}$ or $\Sigma^{*} - w$ depending on whether $M$ halts. These are both regular languages and so if we could exhibit a regular grammar we could decide the halting problem. The full proof is in Shallit's book http://www.amazon.co.uk/Second-Course-Formal-Languages-Automata/dp/0521865727
Sam Jones
CC BY-SA 4.0
2024-03-28T04:36:07.083Z
@SamJones Is that still true for deterministic CFLs?
Antimony
CC BY-SA 3.0
2015-03-12T00:18:56.437Z
2015-03-12T00:18:56.437Z
babou
<p>Does anyone know whether the following decision problem is decidable:</p>

<p>Given a context-free language $L$, is $L$ regular?</p>

<p>Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone know an algorithm that takes as input a context-free grammar $G$ and outputs an equivalent regular grammar $G'$, i.e. $L(G) = L(G')$, if $L(G)$ is regular?</p>

CC BY-SA 3.0
2015-03-12T04:19:48.477Z
You could either use [Greibach Theorem](http://en.m.wikipedia.org/wiki/Greibach%27s_theorem) to show it's undecidable, or just notice that universality is undecidable for CFGs, but is decidable for regular languages.
R B
CC BY-SA 3.0
2015-03-12T07:51:52.037Z
Not a research level question.
J.-E. Pin
CC BY-SA 3.0
2015-03-13T08:27:31.513Z
I think this is a pretty interesting (research level) question.  Thanks for asking.  :)
Michael Wehar
CC BY-SA 3.0
2015-03-16T13:01:12.937Z
@RB Indeed, undecidability follows directly from [Greibach's Theorem](http://en.wikipedia.org/wiki/Greibach%27s_theorem). Thanks!
Petar Tsankov
CC BY-SA 4.0
2019-03-02T21:14:59.333Z
@RB I agree about Greibach's theorem, but I believe the two facts about universality are not enough. They can be used to show that it's not possible to *convert* a CFG to a regular language when possible, but this does not yet mean it's undecidable to merely *decide* whether a context-free language is regular.
sdcvvc
<regular-language><context-free><decidability>
Deciding whether a context-free language is regular
Petar Tsankov
# Deciding whether a context-free language is regular

(Asked by: username_0 on 2015-03-11)

Does anyone know whether the following decision problem is decidable:

Given a context-free language $L$, is $L$ regular?

Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone know an algorithm that takes as input a context-free grammar $G$ and outputs an equivalent regular grammar $G'$, i.e. $L(G) = L(G')$, if $L(G)$ is regular?

**Tags:** regular-language, context-free, decidability

> **Comments:**
> **username_1**: You could either use [Greibach Theorem](http://en.m.wikipedia.org/wiki/Greibach%27s_theorem) to show it's undecidable, or just notice that universality is undecidable for CFGs, but is decidable for regular languages.  
> **username_2**: Not a research level question.  
> **username_3**: I think this is a pretty interesting (research level) question.  Thanks for asking.  :)  
> **username_0**: @RB Indeed, undecidability follows directly from [Greibach's Theorem](http://en.wikipedia.org/wiki/Greibach%27s_theorem). Thanks!  
> **username_4**: @RB I agree about Greibach's theorem, but I believe the two facts about universality are not enough. They can be used to show that it's not possible to *convert* a CFG to a regular language when possible, but this does not yet mean it's undecidable to merely *decide* whether a context-free language is regular.  

---

## 1 answers

### Answer by username_5 on 2015-03-12. Score: 10

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.

Regarding DCFL, I have two references (from Hopcroft+Ullman 79):

* [A regularity test for pushdown machines](http://www.sciencedirect.com/science/article/pii/S0019995867905918), R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
* [Regularity and Related Problems for Deterministic Pushdown Automata](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.8903&rep=rep1&type=pdf), Leslie G. Valiant, JACM 1975

Regarding a procedure to get a regular version when possible, I have no suggestion.

> **Comments:**
> **username_6**: The procedure to get a regular grammar can't exist. Given a Turing machine $M$ one can construct a Context-free grammar whose language is either $\Sigma^{*}$ or $\Sigma^{*} - w$ depending on whether $M$ halts. These are both regular languages and so if we could exhibit a regular grammar we could decide the halting problem. The full proof is in Shallit's book http://www.amazon.co.uk/Second-Course-Formal-Languages-Automata/dp/0521865727  
> **username_7**: @SamJones Is that still true for deterministic CFLs?  

---

