Decidable Languages : ACFG, APDA

A language is decidable if there is a Turing Machine that halts and accepts strings that belong to the language, and halts and rejects strings that do not belong to the language.


    \begin{equation*} A_{CFG} = \{ <G, w> : G \text{ is a CFG and } w \in L(G) \} \end{equation*}

There exists a TM that decides the above language. Given the string encoding of a CFG G and some string w, a TM can decide whether G can derive w.

Greibach Normal Form (GNF)

Any CFG can be converted to Greibach Normal Form. In this form, all production rules start with a terminal symbol, optionally followed by some variables. The only exception is the start variable which can go to \epsilon.

Formally, a CFG is in Greibach normal form, if all production rules are of the form

    \begin{equation*} A \to aA_{1}A_{2} \cdots A_{n} \end{equation*}


    \begin{equation*} S \to \epsilon \end{equation*}

where A is a nonterminal symbol, a is a terminal symbol, A_{1}A_{2}\ldots A_{n} is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and \epsilon is the empty word.

One interesting property about a grammar in this form is related to parsing. Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n.

High-Level Description

On input <G, w>

  1. Check whether <G> indeed encodes a CFG. If not, reject.
  2. Convert G to a CFG, G' in GNF.
  3. If w = \epsilon, check if the rule S \to \epsilon is present in G'. If yes, accept. Else reject.
  4. Let n = |w|.
  5. Examine all derivations using n applications of rules in G'. If any derivation produces w accept. Else reject.

Since all these steps take a finite amount of time, it is guaranteed that the machine halts and decides.

Any PDA can be converted to an equivalent CFG. Thus, the following language is also decidable since it reduces to A_{CFG}.


    \begin{equation*} A_{PDA} = \{ <P, w> : P \text{ is a PDA and } w \in L(P) \} \end{equation*}

Leave a Reply

Your email address will not be published. Required fields are marked *