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.