<?xml version="1.0" encoding='utf-8'?>
<!DOCTYPE wml PUBLIC "-//WAPFORUM//DTD WML 1.1//EN" "http://www.wapforum.org/DTD/wml_1.1.xml">
<wml>
<card id="card1" title="Context-free language - Page 13 - Wikipedia">
<p>
<a accesskey="1" href="page.php?w=context-free_language&amp;p=12">1.Previous</a><br />
<a accesskey="3" href="page.php?w=context-free_language&amp;p=14">3.Next</a>
</p>
<p>and a regular language is context-free, hence the variant of the problem where B is a regular grammar is decidable (see "Emptiness" below).<br/>
*Containment: is  ? Again, the variant of the problem where B is a regular grammar is decidable, while that where A is regular is generally not.<br/>
*Universality: is ?<br/>
*Regularity: is  a regular language?<br/>
*Ambiguity: is every grammar for  ambiguous?</p>

<p>The following problems are decidable for arbitrary context-free languages:<br/>
*Emptiness: Given a context-free grammar A, is  ?<br/>
*Finiteness:</p><p>
<a accesskey="1" href="page.php?w=context-free_language&amp;p=12">1.Previous</a><br />
<a accesskey="3" href="page.php?w=context-free_language&amp;p=14">3.Next</a>
</p>

<do type="prev" label="Search">
        <go href="search.wml"/>
</do>

</card>
</wml>
