I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means.

I know that generation of a particular string by a given CFG is a decidable problem. This means that we can design a TM that will definitely halt and tell us whether the given string is generated by a CFG.

But coming to this problem, what does it mean? I am making the interpretation that this means - The problem of determining whether a given arbitrary language is a CFL is decidable.

Am I right or does it mean something else?


The phrase

Every context-free language is decidable

has the following meaning:

If the language $L$ is context-free, then $L$ is decidable

or in other words

If $L$ is a context-free language then $L$ is a decidable language

  • $\begingroup$ I get that. But what does decidability mean in terms of a CFL? Does it mean that I can design a TM to show whether any given language is a CFL or not? $\endgroup$ – Hrishikesh Athalye Apr 27 '20 at 7:43
  • 3
    $\begingroup$ I assume that you have seen in class a definition of the following two concepts: "context-free language", "decidable language". Your phrase means "if a language satisfies the definition of a context-free language, then it also satisfies the definition of a decidable language". No more, no less. $\endgroup$ – Yuval Filmus Apr 27 '20 at 7:45

It means for every context free language there is an algorithm that can correctly decide if any string S is in the language or not.

We can actually say something a lot stronger: There is actually a known algorithm that can take an arbitrary context free language and a string as input and decide in polynomial time whether the string is in the language.


A "language" is a set of words over a finite alphabet $\Sigma$ to define a language we have to make an extra step. Take the following definitions s $$L_0 = \{\}$$ $$L_1 = \Sigma$$ $$L_{n+1} = \{(c, w) \mid c \in \Sigma \land w \in L_n\}$$

Note that $(c, w)$ is usually denoted simply as $cw$ or $c \cdot w$ but for the sake of not introducing notation I chose to use an explicit tuple here.

Each $L_n$ above represents the words formed by letters from sigma of length $n$. We now define the Kleene Closure of \Sigma as follows

$$\Sigma^* = \bigcup_{i=0}^\infty L_i$$

Which is to say $\Sigma^*$ is the set of words of any given length. A language $L$ over an alpha bet $\Sigma$ is any subset of $\Sigma^*$. That is $L \subset \Sigma^*$

There are many ways to define a decidable set but I'll choose one which is language specific here. A language $L$ is decidable if there exists a Turing machine $M$ such that $M(w) = ACCEPT$ accepts IFF $w \in L$ and $M$ always halts. $M(w)$ is defined to be the result of running the Turing machine with the tape initialized to $w$ so either ${REJECT, ACCEPT, or LOOP}$ depending on the outcome.

"CFL" means "Context Free Language". There are also multiple ways to define what a context free language is but natural answer is the set of words that can be produced by production rules in a context free grammar.

So "Every set of words produced by a context free grammar is recognized by some Turing machine" is a more formal way to define things that drills down a little bit. You'll undoubtedly have additional questions about what that statement really means. Eventually you'll just have to read a book.

That's a really formal way to go about it but all this stuff really means is "You can always write a parser for any context free grammar". At least that's how I'd explain it to a programmer.


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.