A Companion to Chomsky. Группа авторов

---

Скачать книгу

---

someone someone really someone really really someone ran and someone someone really ran and someone someone ran someone really ran someone ran and ran someone ran and someone ran someone ran really someone ran really really someone ran and someone ran really someone ran and someone really ran and someone ran and someone ran and someone and someone someone and ran

Stated generally, what we can conclude when two strings have the same forward set is that the relevant grammar treats them as intersubstitutable prefixes. So forward sets describe the way a grammar partitions prefixes into equivalence classes, collections of prefixes that are all intersubstitutable with each other. Table 5.2 shows the classes into which prefixes are partitioned by the grammar in Figure 5.2.

      These intersubstitutability relationships also underlie the way “loops” in the structure of an FSG allow for the generation of infinitely many strings. A consequence of the loops in Figure 5.2 is that, for example, someone really and someone really really have the same forward set (namely ). Since these are therefore intersubstitutable, it follows that they are also both interchangeable with someone really really really – since we can substitute someone really really for the someone really part of itself. Any continuation that is compatible with one of these strings (e.g. the continuation ran) will be compatible with all others from the infinite class as well.

Figures 5.4 and 5.5 show some more abstract examples to sharpen these important points.

The grammar in Figure 5.4 requires that a occurs an odd number of times. Here, “what matters” about a prefix is just whether a occurs an odd or even number of times. The grammar reflects this by grouping all strings with an even number of as together in the equivalence class represented by the forward set ; and similarly, for an odd number, the forward set . See Table 5.3.

Figure 5.4 Two representations of a finite‐state grammar requiring an odd number of as

Figure 5.5 Two representations of a finite‐state grammar requiring that the second‐last symbol is a

Table 5.3 Equivalence classes induced by the grammar in Figure 5.4

Contains an even number of as	FORWARD SET:
	EXAMPLE STRINGS: , b, bb, aa, baa, aba, aab, abba
Contains an odd number of as	FORWARD SET:
	EXAMPLE STRINGS: a, ab, ba, bab, bba, aaa, aaba, baaa

The grammar in Figure 5.5 requires that a be the second last symbol in a string. Part of what matters here is whether a was the second last symbol; we also need to track whether the last symbol was a, so that we know where we stand if one more symbol is added. These two yes‐no questions create a four‐way split, represented by the four forward sets shown in Table 5.4. The set of all possible strings is partitioned into these four classes, and knowing which of these four classes a string belongs to provides everything an automaton needs to know in order to enforce appropriate requirements on what follows. For example, any two strings with a in the last position but not the second last position will both have forward set Скачать книгу