http:^^www.cs.washington.edu^education^courses^322^96w^midtermsoln^midtermsoln.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 104 行
HTML
104 行
Date: Wed, 08 Jan 1997 20:48:52 GMTServer: NCSA/1.4.2Content-type: text/html<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN"><!Converted with LaTeX2HTML 95 (Thu Jan 19 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HEAD><TITLE>CSE 322 Midterm Solutions Winter Quarter, 1996</TITLE></HEAD><BODY><meta name="description" value="CSE 322 Midterm Solutions Winter Quarter, 1996"><meta name="keywords" value="midtermsoln"><meta name="resource-type" value="document"><meta name="distribution" value="global"><P> <BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A> <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif"> <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif"> <BR><B> Next:</B> <A NAME=tex2html2 HREF="node1.html"> About this document </A><BR> <HR> <P><P><H1>CSE 322 Midterm Solutions Winter Quarter, 1996</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P><OL><LI>We will use the technique given in the handout and explained by JimFix to construct a regular grammar for <IMG ALIGN=MIDDLE ALT="" SRC="img1.gif">.Since we eventually need to generate a unique set of non-terminals for each <b>a</b> and <b>b</b> in the regular expression, we annotate the expressionwith indices: <IMG ALIGN=MIDDLE ALT="" SRC="img2.gif">. These indices aren'tintended to mean anything, but we'll use them for bookeeping as we develop the grammar. For each set of productions, we denote any starting symbol<b>S</b> as <IMG ALIGN=BOTTOM ALT="" SRC="img3.gif">. If any nonterminal and its productions can be eliminated because it is unreachable from the starting symbol, it is marked with <IMG ALIGN=MIDDLE ALT="" SRC="img4.gif">.<P><IMG ALIGN=BOTTOM ALT="" SRC="img5.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img6.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img7.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img8.gif"><P><IMG ALIGN=BOTTOM ALT="" SRC="img9.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img10.gif"><IMG ALIGN=BOTTOM ALT="" SRC="img11.gif"><P>Thus the final grammar constructed is:<P><IMG ALIGN=BOTTOM ALT="" SRC="img12.gif"><P><LI><IMG ALIGN=MIDDLE ALT="" SRC="img13.gif">.<P><IMG ALIGN=BOTTOM ALT="" SRC="img14.gif">.Each production is used once.<P><LI><IMG ALIGN=MIDDLE ALT="" SRC="img15.gif">.<P><LI>With start symbol <IMG ALIGN=MIDDLE ALT="" SRC="img16.gif"> the grammar is:<P><P><IMG ALIGN=BOTTOM ALT="" SRC="img17.gif"><P><P>The meaning of <IMG ALIGN=MIDDLE ALT="" SRC="img18.gif"> is that the number of <b>a</b>'s generated by <IMG ALIGN=MIDDLE ALT="" SRC="img19.gif"> isequal to <IMG ALIGN=BOTTOM ALT="" SRC="img20.gif">.<P><LI> The fact we are trying to prove is that if <IMG ALIGN=MIDDLE ALT="" SRC="img21.gif"> hasan equal number of <b>a</b>'s as <b>b</b>'s then <IMG ALIGN=BOTTOM ALT="" SRC="img22.gif">. Thiswill be proved by induction on <b>n</b> where <b>|x| = 2n</b>.<OL><LI>The basis is <b>n=0</b>. The only string of length <b>0</b> is <IMG ALIGN=BOTTOM ALT="" SRC="img23.gif">. <IMG ALIGN=BOTTOM ALT="" SRC="img24.gif"> in one step.<LI>The inductive hypothesis is: If <b>w</b> is a string in <IMG ALIGN=MIDDLE ALT="" SRC="img25.gif"> with an equalnumber of <b>a</b>'s as <b>b</b>'s and <b>|w| < 2n</b>, then <IMG ALIGN=BOTTOM ALT="" SRC="img26.gif">.<LI>Case 1 of the induction step. Recall that we are assuming that<b>x</b> has an equal number of <b>a</b>'s as <b>b</b>'s, <b>|x| = 2n</b> and <b>n > 0</b>.In case 1 there is a string <b>y</b> such that <b>x =yz</b>, <b>y</b> hasan equal number of <b>a</b>'s as <b>b</b>'s, <IMG ALIGN=MIDDLE ALT="" SRC="img27.gif">, and <IMG ALIGN=MIDDLE ALT="" SRC="img28.gif">.<P>Since both <b>x</b> and <b>y</b> have an equal number of <b>a</b>'s as <b>b</b>'s thenit must be the case that <b>z</b> does also.Since <IMG ALIGN=MIDDLE ALT="" SRC="img29.gif"> then <b>|y| < 2n</b>. Since <IMG ALIGN=MIDDLE ALT="" SRC="img30.gif"> then itmust be the case that <b>|z| < 2n</b>. Thus, both <b>y</b> and <b>z</b> satisfy thehypothesis of the inductive hypothesis. Hence, <IMG ALIGN=MIDDLE ALT="" SRC="img31.gif"> and <IMG ALIGN=BOTTOM ALT="" SRC="img32.gif">. By using thefirst production with these two derivations we have the derivation.<P><IMG ALIGN=BOTTOM ALT="" SRC="img33.gif"><P></OL></OL><BR> <HR><UL> <LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000"> About this document ... </A></UL><BR> <HR><A NAME=tex2html1 HREF="node1.html"><IMG ALIGN=BOTTOM ALT="next" SRC="http://www.cs.washington.edu/general/latex2html_icons//next_motif.gif"></A> <IMG ALIGN=BOTTOM ALT="up" SRC="http://www.cs.washington.edu/general/latex2html_icons//up_motif_gr.gif"> <IMG ALIGN=BOTTOM ALT="previous" SRC="http://www.cs.washington.edu/general/latex2html_icons//previous_motif_gr.gif"> <BR><B> Next:</B> <A NAME=tex2html2 HREF="node1.html"> About this document </A><BR> <HR> <P><BR> <HR><P><ADDRESS><I>James Fix <BR>Mon Feb 5 14:00:23 PST 1996</I></ADDRESS></BODY>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?