http:^^www.cs.washington.edu^education^courses^322^96w^hw8soln^hw8soln.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 123 行
HTML
123 行
Date: Wed, 08 Jan 1997 20:38:01 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 Assignment 8 Solution Set Wednesday, February 28, 1996</TITLE></HEAD><BODY><meta name="description" value="CSE 322 Assignment 8 Solution Set Wednesday, February 28, 1996"><meta name="keywords" value="hw8soln"><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 Assignment 8 Solution Set Wednesday, February 28, 1996</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P><OL><LI> Consider the NFA <IMG ALIGN=MIDDLE ALT="" SRC="img1.gif"> where <IMG ALIGN=BOTTOM ALT="" SRC="img2.gif"> is given by the table:<P><IMG ALIGN=BOTTOM ALT="" SRC="img3.gif"><P><P>We can construct a DFA <IMG ALIGN=MIDDLE ALT="" SRC="img4.gif"> where <IMG ALIGN=MIDDLE ALT="" SRC="img5.gif"> is given by the table (using the subset construction):<P><IMG ALIGN=BOTTOM ALT="" SRC="img6.gif"><P><P>and where <IMG ALIGN=MIDDLE ALT="" SRC="img7.gif"> and<IMG ALIGN=MIDDLE ALT="" SRC="img8.gif">.<P><LI> Below are the steps for converting the NFA of problem 1 into a regularexpression. We start with the original NFA:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfao.gif"></center><P>First, we make a new start state that has no incoming arcs:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfas.gif"></center><p>Next, make a new final state with no outgoing arcs:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfaf.gif"></center><P>Eliminate a state. The state <IMG ALIGN=MIDDLE ALT="" SRC="img9.gif"> looks like a good candidate:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfaq0.gif"></center><p>Eliminate state <IMG ALIGN=MIDDLE ALT="" SRC="img10.gif">:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfaq2.gif"></center><p>Eliminate <IMG ALIGN=MIDDLE ALT="" SRC="img11.gif">:<br><center><IMG ALIGN=MIDDLE SRC="hw8dfaq1.gif"></center><p>Accounting for the final start state, the equivalent regular expression is<IMG ALIGN=MIDDLE ALT="" SRC="img12.gif">. This can be simplified to<IMG ALIGN=MIDDLE ALT="" SRC="img13.gif">.<LI> <b> Proof that that regular languages are closed under reversal:</b>Suppose the language <b>L</b> over <IMG ALIGN=BOTTOM ALT="" SRC="img14.gif"> is regular. It must be accepted by some NFA <IMG ALIGN=MIDDLE ALT="" SRC="img15.gif">. Consider the NFA <IMG ALIGN=MIDDLE ALT="" SRC="img16.gif"> where<P><IMG ALIGN=BOTTOM ALT="" SRC="img17.gif"><P><P>We will show that <IMG ALIGN=BOTTOM ALT="" SRC="img18.gif"> accepts <IMG ALIGN=BOTTOM ALT="" SRC="img19.gif"> with the following behavioral lemma:<P><b> Behavioral Lemma:</b> For all <IMG ALIGN=MIDDLE ALT="" SRC="img20.gif">, <IMG ALIGN=MIDDLE ALT="" SRC="img21.gif"><IMG ALIGN=MIDDLE ALT="" SRC="img22.gif"> if and only if <IMG ALIGN=MIDDLE ALT="" SRC="img23.gif">.<P>Given that this lemma is true, we can prove that <IMG ALIGN=MIDDLE ALT="" SRC="img24.gif">.Suppose <IMG ALIGN=MIDDLE ALT="" SRC="img25.gif"> and <IMG ALIGN=MIDDLE ALT="" SRC="img26.gif">. Let <b>x = ay</b> for <IMG ALIGN=MIDDLE ALT="" SRC="img27.gif">and <IMG ALIGN=MIDDLE ALT="" SRC="img28.gif">. Note that <IMG ALIGN=MIDDLE ALT="" SRC="img29.gif">. It follows that:<P><IMG ALIGN=BOTTOM ALT="" SRC="img30.gif"><P><P>Suppose that <IMG ALIGN=MIDDLE ALT="" SRC="img31.gif"> and <IMG ALIGN=MIDDLE ALT="" SRC="img32.gif">. Again, let <b>x=ay</b>:<P><IMG ALIGN=BOTTOM ALT="" SRC="img33.gif"><P><P>Consider when <IMG ALIGN=BOTTOM ALT="" SRC="img34.gif">:<P><IMG ALIGN=BOTTOM ALT="" SRC="img35.gif"><P><P>Combining these observations, we have <IMG ALIGN=MIDDLE ALT="" SRC="img36.gif">, and so there is an NFA that accepts <IMG ALIGN=BOTTOM ALT="" SRC="img37.gif">.Thus, if <b>L</b> is regular, <IMG ALIGN=BOTTOM ALT="" SRC="img38.gif"> is regular.</OL><BR> <HR><UL> <LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000"> About this document ... </A></UL><BR> <HR><P><ADDRESS><I>James Fix <BR>Wed Feb 28 11:09:35 PST 1996</I></ADDRESS></BODY>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?