I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.

My question is, why is regularity decidable for DCFLs and undecidable for CFLs?

  • $\begingroup$ Also on Mathematics: math.stackexchange.com/questions/4274990/… $\endgroup$ Oct 13 at 15:19
  • $\begingroup$ DCFLs are less expressive than CFLs, so it's small wonder that some problems are easier for DCFLs. Taking it into an extreme, deciding regularity of the language generated by a regular grammar is even easier. Beyond this general sentiment, you would have to look at the proofs, and see where they go awry for the other class. $\endgroup$ Oct 14 at 5:38

Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement.

The undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and (2) universality, i.e., equality to $\Sigma^*$, is undecidable.

To the contrary, DCFL (1) are not closed under union, (2) have decidable universality. The latter for instance, because DCFL are closed under complement, and emptiness is decidable (in fact for all CFL).

  • $\begingroup$ why are you not considered intersection case? $\endgroup$
    – Punia
    Oct 13 at 19:16
  • $\begingroup$ DCFL are not closed under union that doesn't mean regular? How can you say it is decidable please explain? $\endgroup$
    – Punia
    Oct 13 at 20:15
  • $\begingroup$ Both these classes are not closed under intersection. That property is not relevant in proving (un)decidability. $\endgroup$ Oct 13 at 22:19
  • $\begingroup$ Both closure under union and decidability of universality are used in the proof of undecidability of regularity for CFL. As DCFL does not have both these properties that approach cannot work there. The proof that regularity for DCFL is decidable seems to be rather involved, and I cannot help you there. I only tried to stress why the undecidability proof for CFL could not be extended to DCFL. $\endgroup$ Oct 13 at 22:26
  • $\begingroup$ you answer is very vague to understand. If you have any logic why we take Union, universality to prove decidability, please explain. $\endgroup$
    – Punia
    Oct 14 at 5:59

Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class.

Regularity of the language generated by a CFG

The proof that regularity of the language generated by a CFG is undecidable is very similar to the proof that universality of the language generated by a CFG is undecidable, so we'll start with the latter. The proof proceeds by reduction from the halting problem. Given a Turing machine $M$, we construct a context-free grammar $G$ with the following property:

  • If $M$ doesn't halt on the empty input, then $G$ is universal, that is, $L(G) = \Sigma^*$.
  • If $M$ does halt on the empty input, then $L(G) = \Sigma^* \setminus \{t\}$, where $t$ is a transcript of the execution of $M$ on the empty input.

We encode transcripts as sequences of configurations: $c_1 \# c_2 \# \cdots \# c_n$. Here each $c_i$ is a configuration (the contents of the tape together with the location of the head and the current state), and $c_{i+1}$ is the configuration following $c_i$. The grammar $G$ describes all strings which are not transcripts of halting executions. A string fails to be such a transcript if one of the following cases holds:

  • It is not of the form $c_1\#c_2\#\cdots\#c_n$, where $c_1,\ldots,c_n$ are valid configurations.
  • The transcript is of the form $c_1\#c_2\cdots\#c_n$, where $c_1$ is not a valid initial configuration.
  • The transcript is of the form $c_1\#c_2\cdots\#c_n$, where $c_n$ is not a valid halting configuration.
  • The transcript is of the form $c_1\#c_2\cdots\#c_n$, and for some $i$, the configuration $c_{i+1}$ doesn't follow from the configuration $c_i$.

The first three cases represent regular constraints, and see are easy to handle (and could be handled by a DPDA). The problematic case is the final one: while it is easy to describe bad stretches of the form $\#c_i\#c_{i+1}\#$, the grammar has to "guess" the value of $i$. Indeed, consider the special case $n=3$, and take the point of view of a PDA. The PDA has to guess whether it should be comparing $c_1$ to $c_2$, or whether it should skip $c_1$ and instead compare $c_2$ to $c_3$. This is something that a DPDA cannot do.

From universality to regularity. In the construction outlined above, the language $L(G)$ is regular in both cases. However, given $G$, we can construct another grammar $G'$ that accepts the language $$ \{a^n b^m \# w : n,m \ge 0, w \in L(G)\} \cup \{a^n b^n \# w : n \ge 0, w \in \Sigma^*\} $$ By construction,

  • If $M$ doesn't halt on the empty input then $L(G') = a^*b^*\#\Sigma^*$, which is regular.
  • If $M$ does halt on the empty input then $L(G') = \Sigma^* \setminus \{a^nb^m\#t : n \neq m\}$, which isn't regular.

Regularity of the language accepted by a DPDA

There are several proofs that the regularity of the language accepted by a DPDA is decidable. Here I will outline the original proofs of Stearns and Valiant, but a newer and more efficient algorithm of Shankar and Adiga, A graph-based regularity test for deterministic context-free languages, should also be mentioned.

Given a DPDA, we would like to show that if the language it accepts is regular, then it is accepted by a DFA with at most $N$ many states, where $N$ is a quantity that depends in some explicit computable way on the number of states, number of state symbols, and maximum number of symbols pushed at a single step of the DPDA.

Suppose we somehow showed that. How do we proceed? We go over all DFAs having at most $N$ many states, and for each one, check whether it accepts the same language as the DPDA. Denote the DPDA by $P$ and the candidate DFA by $D$. We first check whether $L(P) \cap \overline{L(D)} = \emptyset$, that is, whether $L(D) \subseteq L(P)$. We can do this by combining three constructions:

  1. Given a DFA, we can construct a DFA for the complement language.
  2. Given a PDA and a DFA, we can construct a PDA for the intersection language.
  3. Given a PDA, we can solve the emptiness problem, that is, determine whether the language is empty.

We then check whether $\overline{L(P)} \cap L(D) = \emptyset$ using a similar approach, crucially using the fact that given a DPDA, we can construct a DPDA for the complement language. If both tests pass, then $L(P) = L(D)$.

In contrast, CFLs are not closed under complementation, and in particular, given a PDA, we cannot in general construct a PDA for the complement language. Moreover, as shown above, we cannot decide if a PDA generates the same language as a given DFA; indeed, even the special case of universality is undecidable.

Now let us go back to the first part of the proof, in which we give a bound on the number of states in an equivalent DFA. Unfortunately this part of the proof is somewhat complicated. Roughly speaking, we show that if at some point of the execution the stack is very deep, then the first few symbols on the stack are too deep to make a difference; otherwise, we can "pump" the input in some way that guarantees that the language accepted by the DPDA is not regular. This implies that in order to simulate the DPDA, it suffices to keep track of a constant number of symbols on the stack, which a DFA can do.

The undecidability proof for CFGs shows that a similar statement is wrong for PDAs. More accurately, while there is still a bound on the number of states in an equivalent DFA, it cannot be computed from the complexity parameters of the PDA since it grows too fast. Indeed, for the grammar $G$ we construct in the undecidability proof, in the case where the machine $M$ halts, the size of the equivalent DFA is essentially the same as the size of the transcript $t$, and so it grows faster than the number of steps it takes $M$ to halt. The maximal number of steps in an equivalent minimal DFA is thus some sort of busy beaver function, which grows too fast to be computable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.