I. Decision Properties

<aside> <img src="/icons/bell-off_orange.svg" alt="/icons/bell-off_orange.svg" width="40px" /> Non-Decision Properties

Many questions that can be decided for regular sets cannot be decided for CFL’s

• Are two CFL’s the same?
• Are two CFL’s disjoint?

Need theory of Turing machines and decidability to prove no algorithm exists.

</aside>

1. Emptiness

We’ve learned to eliminate useless variables,

and if the start symbol is among them, then the CFL is empty; otherwise not.

2. Membership

Want to know if string $w$ is in $L(G)$.

Assume $G$ is in CNF.

• Or convert the given grammar to CNF.
• $w = ε$ is a special case, solved by testing if the start symbol is nullable.

CYK Algorithm

1. Let $w = a_1…a_n$.
2. We construct an n-by-n triangular array of sets of variables.
3. $X_{ij}= \{\text{variables } A | A \Rightarrow^* a_i…a_j\}$
4. Induction on $\tt (j–i)+1$ (the length of the derived string).
5. Finally, ask if $S$ is in $X_{1n}$.

Basis:

$X_{ii}= \{A | A \rightarrow a_i\text{ is a production}\}$