{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e上下文无关文法是一种强大的描述语言的方法。许多编程语言的语法,包括在这个在线评测系统上提供了编译器的C、C++、Java和Pascal,都是用上下文无关文法指定的。\u003c/p\u003e\u003cp\u003e在这个题目中,我们用一种生成式的观点来看待上下文无关文法。一个上下文无关文法由一组用以改写符号串的\u003ci\u003e生成规则\u003c/i\u003e组成。每一条生成规则都有这样的形式:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003eV\u003c/i\u003e → \u003ci\u003ew\u003c/i\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e其中\u003ci\u003eV\u003c/i\u003e是一个\u003ci\u003e符号\u003c/i\u003e,\u003ci\u003ew\u003c/i\u003e是一个符号串。符号被分成终结符号和变元两种。在上面的规则里,\u003ci\u003eV\u003c/i\u003e必须是一个变元,而\u003ci\u003ew\u003c/i\u003e可以包含变元和/或终结符号。“上下文无关”表达出这样一个事实:\u003ci\u003eV\u003c/i\u003e总是可以被替换成\u003ci\u003ew\u003c/i\u003e,无论它在什么上下文中出现。在所有变元中,有一个被指定为开始变元。利用一个上下文无关文法生成一个串,首先要从包含单个开始变元的串开始,连续和任意得应用规则改写串,直到只剩下终结符号。\u003c/p\u003e\u003cp\u003e例如,字母表只包含\u003ccode\u003ez\u003c/code\u003e,开始变元是\u003ci\u003eS\u003c/i\u003e,有下列规则:\u003c/p\u003e\u003col\u003e\u003cli\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003eCB\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003eZZ\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eA\u003c/i\u003e → \u003ci\u003eCB\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eA\u003c/i\u003e → \u003ci\u003eZZ\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eB\u003c/i\u003e → \u003ci\u003eZZ\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eC\u003c/i\u003e → \u003ci\u003eBA\u003c/i\u003e\u003c/li\u003e\u003cli\u003e\u003ci\u003eZ\u003c/i\u003e → \u003ccode\u003ez\u003c/code\u003e\u003c/li\u003e\u003c/ol\u003e\u003cp\u003e那么我们从\u003ci\u003eS\u003c/i\u003e开始,然后选择一个规则来应用。如果我们选择规则1, 就将\u003ci\u003eS\u003c/i\u003e替换成\u003ci\u003eCB\u003c/i\u003e,得到串\u003ci\u003eCB\u003c/i\u003e。然后,如果我们选择规则6,就将\u003ci\u003eC\u003c/i\u003e替换成\u003ci\u003eBA\u003c/i\u003e,得到串\u003ci\u003eBAB\u003c/i\u003e。如果我们现在选择规则4,就将\u003ci\u003eA\u003c/i\u003e替换成\u003ci\u003eZZ\u003c/i\u003e,得到串\u003ci\u003eBZZB\u003c/i\u003e。我们可以用符号来更简洁的表示这一系列选择:\u003ci\u003eS\u003c/i\u003e ⇒ \u003ci\u003eCB\u003c/i\u003e ⇒ \u003ci\u003eBAB\u003c/i\u003e ⇒ \u003ci\u003eBZZB\u003c/i\u003e ⇒ \u003ci\u003eZZZZB\u003c/i\u003e ⇒ \u003ci\u003eZZZZZZ\u003c/i\u003e ⇒ \u003ccode\u003ez\u003c/code\u003e\u003ci\u003eZZZZZ\u003c/i\u003e ⇒ \u003ccode\u003ezz\u003c/code\u003e\u003ci\u003eZZZZ\u003c/i\u003e ⇒ \u003ccode\u003ezzz\u003c/code\u003e\u003ci\u003eZZZ\u003c/i\u003e ⇒ \u003ccode\u003ezzzz\u003c/code\u003e\u003ci\u003eZZ\u003c/i\u003e ⇒ \u003ccode\u003ezzzzz\u003c/code\u003e\u003ci\u003eZ\u003c/i\u003e ⇒ \u003ccode\u003ezzzzzz\u003c/code\u003e。这个文法的语言就是所有由一个奇数的两倍那么多个\u003ccode\u003ez\u003c/code\u003e组成的串的集合。\u003c/p\u003e\u003cp\u003e给出一个上下文无关语言和一些串,判定这些串是否属于这个文法的语言。\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e为简洁其见,我们将上下文无关文法中所有“→”左边的变元相同的的规则组合到一起。例如,我们将下面三条规则\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003eu\u003c/i\u003e\u003cbr\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003ev\u003c/i\u003e\u003cbr\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003ew\u003c/i\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e组合成\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003eS\u003c/i\u003e → \u003ci\u003eu\u003c/i\u003e | \u003ci\u003ev\u003c/i\u003e | \u003ci\u003ew\u003c/i\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e上下文无关文法用一种称为\u003ci\u003eChomsky范式\u003c/i\u003e的特殊形式给出。用Chomsky范式给出的上下文无关文法只包含如下形式的规则:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003eA\u003c/i\u003e → \u003ci\u003eBC\u003c/i\u003e\u003cbr\u003e\u003ci\u003eA\u003c/i\u003e → \u003ci\u003ea\u003c/i\u003e\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e其中\u003ci\u003ea\u003c/i\u003e是任意终结符号,\u003ci\u003eA\u003c/i\u003e、\u003ci\u003eB\u003c/i\u003e、和\u003ci\u003eC\u003c/i\u003e是任意变元,但\u003ci\u003eB\u003c/i\u003e和\u003ci\u003eC\u003c/i\u003e不能是开始变元。Chomsky范式还允许规则\u003ci\u003eS\u003c/i\u003e → \u003ci\u003eε\u003c/i\u003e, 其中\u003ci\u003eS\u003c/i\u003e是开始变元,\u003ci\u003eε\u003c/i\u003e表示空串,使得上下文无关文法可以产生空串。在这个题目中我们忽略这种情况。\u003c/p\u003e\u003cp\u003e输入用Chomsky范式给出一个上下文无关文法和不超过50个串。我们用单个小写字母作为终结符号,当个大写字母作为变元。\u003ci\u003eS\u003c/i\u003e总是被看作开始符号。文法用若干行给出。每一行包含按上述方式组合成的同一个变元的生成规则。“→”将会被替换成“\u003ccode\u003e-\u0026gt;\u003c/code\u003e”。不是所有可能的变元都会在文法中出现,但每个出现的变元都会有至少一条规则。包含单个“\u003ccode\u003e#\u003c/code\u003e”的一行表示文法的结束。在文法后面,每行包含一个串。当再不能找到任何串时输入结束。空格和空行不会在输入中出现。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e为每个串输出一行。如果一个串属于给定的上下文无关文法的语言,输出“\u003ccode\u003eYES\u003c/code\u003e”(不包含括号),否则输出“\u003ccode\u003eNO\u003c/code\u003e”(不包含括号)。\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eS-\u0026gt;CB|ZZ\r\nA-\u0026gt;CB|ZZ\r\nB-\u0026gt;ZZ\r\nC-\u0026gt;BA\r\nZ-\u0026gt;z\r\n#\r\nzzzzzz\r\nz\r\na\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\r\nNO\r\nNO\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}