《递归下降分析 (21).ppt》由会员分享，可在线阅读，更多相关《递归下降分析 (21).ppt（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、compilerS1Minimizing Number of StatesoThe resulting DFA may be more complex than necessary.nIn Example 2.15 we got DFA for a*,but there is a more simple DFA.oImportant result from automata theory:For any given DFA there is an equivalent DFA containing a minimum number of states,and it is unique.1,2,
2、42,3,4aaacompilerS2Minimizing Number of States Algorithm1.Create two sets of states:all accepting states and all non-accepting states.2.For each set of states,consider the transitions on each character a of the alphabet.If all states in the set have transitions on a to the same set of states,then it
3、 defines a-transition from the set of states to itself.If there are two states in the set s and t that have transitions on a that land in different sets,we must split the set of states into two sets according to where a-transitions land.3.Repeat step 2 until either all states contain one element or
4、no further splitting pilerS3Example 2.1812,3,4,5,7,104,5,6,7,9,104,5,7,8,9,10letterletterletterletterdigitdigitdigitletter letterdigitcompilerS4Example 2.19o(a|)b*oAll states are accepting states.Each accepting state has a b-transition to another accepting state.oa distinguishes state 1 from states 2 and 3.nThere is a-transition to error state from 2 and 3123abbb12,3abbb