What does “Every CFL is decidable” exactly mean?

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.