Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Context-Free Languages
Description
In this problem, we work with CFGs in a generative manner. A CFG consists of a set of
where For example, the alphabet of terminals consists of *S*→*CB**S*→*ZZ**A*→*CB**A*→*ZZ**B*→*ZZ**C*→*BA**Z*→`z`
then we start with Given a CFG and some strings, determine whether each string belongs to the language of the grammar. Input 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
into
And the CFG is given in a special form called
where 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. Output For each string, output exactly one line. If the string belongs to the language of the given CFG, the line should read “ Sample Input S->CB|ZZ A->CB|ZZ B->ZZ C->BA Z->z # zzzzzz z a Sample Output YES NO NO Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator