# What does “Every CFL is decidable” exactly mean?

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?

• – D.W. Apr 27 at 7:29

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

• 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? – Hrishikesh Athalye Apr 27 at 7:43
• 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. – Yuval Filmus Apr 27 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.