编程介的小学生 2017-02-25 14:51 采纳率: 20.5%
浏览 835
已采纳

Language Cardinality

A (formal) language is a set of strings. One way to define a particular langauge is using ordinary set notation. Alternatively, some form of grammar may be more convenient for representing large sets. The UW grammar in which we are interested has two parts:

An initial string
A set of replacement rules of the form s1 -> s2 where s1 and s2 are strings
The language defined by this grammar is the set of all strings that can be generated by repeatedly replacing s1 by s2 within the initial string. For example, consider the grammar G consisting of the initial string

"AyB"

and the replacement rules

{"A"->"ab", "Ay"->"cdy", "B"->"w", "B"->"x"} .

G generates the language

L = {"AyB", "Ayw", "Ayx", "abyB", "abyw", "abyx", "cdyB", "cdyw", "cdyx"}

Given a UW grammar G, compute how many different strings there are in the language generated by G.

Input

The first line of input contains the initial string. The second and subsequent lines contain the replacement rules, one per line. There are at most 100 replacement rules. Each input string contains between 0 and 10 upper and lower case letters, and is enclosed in quotes. There are no spaces in the input.

Input contains multiple test cases. Subsequent test cases are separated with a single blank line.

Output

Output consists of a single integer, the number of distinct strings in the language generated by G. If there are more than 1000 distinct strings, print "Too many." instead.

Sample Input

"AyB"
"A"->"ab"
"Ay"->"cdy"
"B"->"w"
"B"->"x"

Sample Output

9

  • 写回答

2条回答 默认 最新

  • threenewbee 2017-03-03 15:45
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥15 state显示变量是字符串形式,但是仍然红色,无法引用,并显示类型不匹配
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波