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.

A_CFG

$\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>$

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