【荐】02形式文法【荐】.pdf

褰㈠紡璇█涓庤嚜鍔ㄦ満 Formal Languages and Automata Theory 绗簩绔 褰㈠紡鏂囨硶 鏁欏笀锛氳儭鏄ユ槑銆佽档姘告湜銆侀倱濠 涓婄珷鍥為【 闆嗗悎锛 瀛楁瘝琛細饊姾 锛屽瓧姣嶈〃鐨勯棴鍖咃細饊姾+, 饊姾鈭 璇█锛氿€伋 鈯 饊姾鈭 锛岃瑷€鐨勯棴鍖咃細饊伋+, 饊伋鈭 绌鸿瑷€锛氿€崜 闆嗗悎鍏冪礌锛 瀛楃涓诧細鈭€聿欚€崘饊姾鈭 , 绌哄瓧绗︿覆锛氿€尯 鍙ュ瓙锛氣垁聿欚€崘饊伋 绗簩绔 褰㈠紡鏂囨硶 褰㈠紡鏂囨硶鍙婂叾娲剧敓璇█ 褰㈠紡鏂囨硶鐨勬瀯閫犱笌绛変环 褰㈠紡鏂囨硶鐨勪箶濮嗘柉鍩轰綋绯 鏈妭璇剧殑瑕佺偣 鏂囨硶鐨勫舰寮忓畾涔堹 饊伄 = 饊伣, 肀? 饊伔, 肀 鏂囨硶鐨勬淳鐢燂紱鎺ㄥ锛涘綊绾 * 缁欏畾鏂囨硶锛屽拰涓€涓彞瀛愶紝缁欏嚭鎺ㄥ鍜屽綊绾 * 缁欏畾鏂囨硶锛屾寚鍑哄叾璇█鐨勭壒寰 鏂囨硶鐨勬瀯閫犱笌绛変环鎬 * 缁欏畾鑷劧鎻忚堪璇█锛屾瀯閫犳枃娉 涔斿鏂熀鐨勬枃娉曚綋绯 褰㈠紡鏂囨硶鍙婂叾娲剧敓璇█ 褰㈠紡鏂囨硶鏄敓鎴愮鍙疯瑷€鐨勪竴绉嶆暟瀛︾郴缁燂細 鐢ㄥ舰寮忓寲鐨勬湁绌锋弿杩版墜娈垫弿杩扮鍙疯瑷€鐨勭粨鏋勭壒寰侊紱 鐢熸垚璇█鐨勬墍鏈夊彞瀛愶紱 鍒ゆ柇鎵€缁欑鍙蜂覆鏄惁涓鸿瑷€鍙ュ瓙锛岃嫢涓嶆槸锛岄敊鍦ㄤ綍澶 涓烘锛岄渶瀹氫箟鍚堝紡姝ｇ‘鐨勫舰寮忔枃娉曘€ 褰㈠紡鏂囨硶鍙婂叾娲剧敓璇█ 瀹氫箟 2.1锛氬舰寮忔枃娉曠殑涓€鑸€у畾涔 褰㈠紡鏂囨硶锛堢畝绉版枃娉曪級琛ㄧ幇涓轰竴涓洓鍏冪粍 饊伄 = (饊伣, 肀? 饊伔, 肀?, 鍏朵腑锛 V锛氬彉鍏冪殑闈炵┖鏈夌┓闆嗭紱鍏朵腑锛屾瘡涓娉曞彉鍏冧唬琛ㄤ竴涓娉曡寖鐣淬€ T锛氱粓鏋佺鐨勯潪绌烘湁绌烽泦锛孷 飪 T = 飪嗐€ P锛氫骇鐢熷紡鐨勯潪绌烘湁绌烽泦锛孭 涓厓绱犱竴鑸舰寮忎负 飦 飩 飦紝璇讳綔锛 飦 瀹氫箟涓猴仮 锛屾垨飦 鍙互鏄仮 锛涘叾涓 + 飦 飪 锛圴 飪 T 锛 锛屼笖飦 涓嚦灏戞湁V 涓竴涓厓绱犲嚭鐜帮紱 飥 飦 飪 锛圴 飪 T 锛 銆 S锛歋 飪嶸 锛屼负寮€濮嬬銆 褰㈠紡鏂囨硶鍙婂叾娲剧敓璇█ 绾﹀畾- 鎸変互涓嬫柟寮忎娇鐢 V 飪 T 涓鍙凤細 鑻辨枃瀛楁瘝杈冧负鍓嶉潰鐨勫ぇ鍐欏瓧姣嶏紝濡侫 锛孊锛孋锛屸€︼紝琛ㄧず璇硶鍙橀噺锛 鑻辨枃瀛楁瘝杈冧负鍓嶉潰鐨勫皬鍐欏瓧姣嶏紝濡俛锛宐锛宑锛屸€︼紝琛ㄧず缁堟瀬绗﹀彿锛 鑻辨枃瀛楁瘝杈冧负鍚庨潰鐨勫ぇ鍐欏瓧姣嶏紝濡 X 锛孻 锛孼 锛屸€︼紝琛ㄧず璇硶鍙橀噺鎴栫粓鏋佺 鍙 鑻辨枃瀛楁瘝杈冧负鍚庨潰鐨勫皬鍐欏瓧姣嶏紝濡倄, y, z, 鈥? 琛ㄧず鐢辩粓鏋佺鍙风粍鎴愮殑绗﹀彿涓 甯岃厞瀛楁瘝飦 锛岋仮锛岋仹锛屸€︼紝琛ㄧず璇硶鍙橀噺鎴栫粓鏋佺鍙风粍鎴愮殑绗﹀彿涓层€ 宸﹂儴鐩稿悓鐨勪骇鐢熷紡锛氾仭 飩 飦 锛岋仭 飩 飦 锛屸€? 飦 飩 飦 1 2 n 鍙啓涓猴細 飦 飩 飦 | 飦 | 鈥 飦 1 2 n 褰㈠紡鏂囨硶鍙婂叾娲剧敓璇█ 渚嬶細璁炬湁鍥涘厓缁 G = 锛坽 A, B, C, E }, { a, b, c }, { S 飩瓵BC | abc, D 飩 e | a, FB飩甤, A飩瓵, E飩產bc |蔚}, S ) 鏄惁涓轰竴鍚堝紡鏂囨硶锛 瀛樺湪闂锛 淇敼锛