例如，设x=abc,y=de,则它们的连接xy=abcde。容易看出xy=x+y.doc

第  PAGE \* MERGEFORMAT 9 页 共  NUMPAGES \* MERGEFORMAT 9 页 例2.1 设x = 001，则有 x0 = ε，x2 = 001001，x3 = 001001001。 例2.2 设 x = abc，则 ?、a、ab及abc 都是x的前缀，其中 ?、a和ab 为 x 的真前缀；而abc、bc、c及? 都是 x 的后缀，其中bc、c和? 为 x 的真后缀。 例如，设 x = abc , 其子串为 abc , ab , bc , a , b , c , ? ， 真子串为 ab , bc , a , b , c , ?。值得注意的是 ac 并不是 x 的子串。 例2.3 设 A = {a, bc} ，B = {de, f} ，则： AB = {ade, af, bcde, bcf} 注意有{?} A = A{?} = A , ?A = A? = ?，其中?为空集。符号串集合的乘积一般不满足交换律。 例2.4设A = {ab, cd}，则 A+ = {ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, … } A* = {?, ab, cd, abab, abcd, cdab, cdcd, ababab, ababcd, … } 例2.5 文法G = (VN,VT, S, P )， 其中： VN = {S, P} VT = {a, b, c, d} P = {S?aPd, S? abcd, S?aSd, P?bPc, P? bc} 在此，有两个非终极符S和P；有四个终极符a、b、c和d；五条产生式；开始符号是S。 该文法可简写为： 文法G: S?aPd | abcd | aSd P?bPc | bc G产生的语言为： L(G) = {anbmcmdn | m,n ≥ 1} 。 例2.6 文法G: S?aSb | ab 容易验证，G为2型文法，G产生的语言为： L(G) = {anbn | n ≥ 1} 例2.7 文法G: S?0S | 0 容易验证，G为3型文法，而且是3型文法中的右线性文法。G产生的语言为： L(G) = {0n | n ≥ 1} 例2.8 文法G: S?S0 | 0 容易验证，G为3型文法，而且是3型文法中的左线性文法。G产生的语言为： L(G) = {0n | n ≥ 1} 例2.9 设有文法G： S ? cAd A ? ab | a 对于符号串$ = cabd，显然存在推导ScAdcabd，则ab是句型cabd相对于A的短语，也是相对于A的直接短语，同时ab也是句型cabd的句柄。 例2.10 设有文法G: A?aBcD B?b | ? D?BB | d 在保持文法等价的情况下消除该文法中的空产生式。 解：? = {B, D}，去掉文法中的空产生式B??，得到的新文法如下： G?: A?aBcD B?b D?BB | d 根据算法中第5步可以增加下列产生式： A?acD A?aBc A?ac D?B 综上，得到的新文法如下： G?: A?aBcD | acD | aBc | ac B?b D?BB | B | d 例2.11 设有如下文法： G： A?B | D | aB B?C | b C?c D?B | d 消除该文法中的特型产生式。 解：?A = {B, D, C} ?B = {C} ?C = { } ?D = {B, C} 根据算法第2步，在文法中补充如下规则： A?b | d | c B?c D?b | c 去掉文法中的特型产生式，得到如下文法： G1：A? aB | b | d | c B? b | c C?c D? d | b | c 再去掉上述文法中的无用产生式，得到最终结果： G2: A?aB | b | d | c B?b | c 若非终极符A的不同产生式的右部具有相同的前缀，这种情形不满足自顶向下的语法分析条件，这时可用提取左因子的方法消除产生式的公共前缀。假定关于Ａ的产生式为： A???1 | ??2 | … | ??n | ?1| ?2 | … | γm (其中每个?i不以?开头) 那么，可以把这些产生式写成: A??A’ | ?1 | γ2 | … | γm A’??1 | ?2 | … | ?n 经过反复提取左因子，就能够使每个非终极符的任意个不同产生式的右部不具有公共前缀。 例2.12 在Pascal语言中，语句和表达式表的产生式都有公共