#P3220. 上下文无关语言

上下文无关语言

Description

上下文无关文法是一种强大的描述语言的方法。许多编程语言的语法,包括在这个在线评测系统上提供了编译器的C、C++、Java和Pascal,都是用上下文无关文法指定的。

在这个题目中,我们用一种生成式的观点来看待上下文无关文法。一个上下文无关文法由一组用以改写符号串的生成规则组成。每一条生成规则都有这样的形式:

Vw

其中V是一个符号w是一个符号串。符号被分成终结符号和变元两种。在上面的规则里,V必须是一个变元,而w可以包含变元和/或终结符号。“上下文无关”表达出这样一个事实:V总是可以被替换成w,无论它在什么上下文中出现。在所有变元中,有一个被指定为开始变元。利用一个上下文无关文法生成一个串,首先要从包含单个开始变元的串开始,连续和任意得应用规则改写串,直到只剩下终结符号。

例如,字母表只包含z,开始变元是S,有下列规则:

  1. SCB
  2. SZZ
  3. ACB
  4. AZZ
  5. BZZ
  6. CBA
  7. Zz

那么我们从S开始,然后选择一个规则来应用。如果我们选择规则1, 就将S替换成CB,得到串CB。然后,如果我们选择规则6,就将C替换成BA,得到串BAB。如果我们现在选择规则4,就将A替换成ZZ,得到串BZZB。我们可以用符号来更简洁的表示这一系列选择:SCBBABBZZBZZZZBZZZZZZzZZZZZzzZZZZzzzZZZzzzzZZzzzzzZzzzzzz。这个文法的语言就是所有由一个奇数的两倍那么多个z组成的串的集合。

给出一个上下文无关语言和一些串,判定这些串是否属于这个文法的语言。

Input

为简洁其见,我们将上下文无关文法中所有“→”左边的变元相同的的规则组合到一起。例如,我们将下面三条规则

Su
Sv
Sw

组合成

Su | v | w

上下文无关文法用一种称为Chomsky范式的特殊形式给出。用Chomsky范式给出的上下文无关文法只包含如下形式的规则:

ABC
Aa

其中a是任意终结符号,AB、和C是任意变元,但BC不能是开始变元。Chomsky范式还允许规则Sε, 其中S是开始变元,ε表示空串,使得上下文无关文法可以产生空串。在这个题目中我们忽略这种情况。

输入用Chomsky范式给出一个上下文无关文法和不超过50个串。我们用单个小写字母作为终结符号,当个大写字母作为变元。S总是被看作开始符号。文法用若干行给出。每一行包含按上述方式组合成的同一个变元的生成规则。“→”将会被替换成“->”。不是所有可能的变元都会在文法中出现,但每个出现的变元都会有至少一条规则。包含单个“#”的一行表示文法的结束。在文法后面,每行包含一个串。当再不能找到任何串时输入结束。空格和空行不会在输入中出现。

Output

为每个串输出一行。如果一个串属于给定的上下文无关文法的语言,输出“YES”(不包含括号),否则输出“NO”(不包含括号)。

S->CB|ZZ
A->CB|ZZ
B->ZZ
C->BA
Z->z
#
zzzzzz
z
a
YES
NO
NO

Source

第六届北京大学程序设计大赛暨ACM/ICPC选拔赛

, frkstyc

Translator

Yingchong SITU 'frkstyc'