|Online Judge||Problem Set||Authors||Online Contests||User|
Context-free grammars (CFG) are a powerful method of describing languages. The syntax of most programming languages including C, C++, Java and Pascal, compilers for which are provided in this online judge system, is specified using CFGs.
In this problem, we work with CFGs in a generative manner. A CFG consists of a set of production rules for transforming strings. Every rule is of the form
where V is a symbol and w is a string of symbols. Symbols are classified into terminals and variables. In the rule above, V is restricted to be a variable, while w can contain terminals and/or variables. The term “context-free” expresses the fact that V can always be replaced by w, regardless of the context in which it occurs. Among variables, exactly one of them is designated as the start variable. To generate a string using the CFG, one begins with a string consisting of only a single start variable, and then applies the rules successively and arbitrarily to rewrite the string until only terminals are left.
For example, the alphabet of terminals consists of
then we start with S, and we can choose a rule to apply to it. If we choose rule 1, we replace S with CB and obtain the string CB. If we then choose rule 6, we replace C with BA and obtain the string BAB. If we now choose rule 4, we replace A with ZZ and obtain the string BZZB. We can write this series of choice more briefly, using symbols: S ⇒ CB ⇒ BAB ⇒ BZZB ⇒ ZZZZB ⇒ ZZZZZZ ⇒
Given a CFG and some strings, determine whether each string belongs to the language of the grammar.
To make everything brief, we group together all rules with the same variable to the left of “→” in the CFG. For example, we group the following three rules
And the CFG is given in a special form called Chomsky normal form (CNF). A CFG in CNF only contains rules of the form
where a is any terminal and A, B, and C are any variables except that B and C may not be the start variable. CNF also permits the rule S → ε, where S is the start variable and ε represents the empty string, so that the CFG can generate the empty string. We ignore this case just for this problem.
The input contains exactly one CFG in CNF and no more than 50 strings. We use single lowercase letters as terminals and single uppercase letters as variables. S will always be the start variable. The CFG is given in several lines. A line contains all production rules for one variable grouped together as described above. “→” will be replaced by “
For each string, output exactly one line. If the string belongs to the language of the given CFG, the line should read “
S->CB|ZZ A->CB|ZZ B->ZZ C->BA Z->z # zzzzzz z a
YES NO NO
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator