http:^^www.cs.washington.edu^education^courses^322^96w^hw10soln^hw10soln.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 86 行
HTML
86 行
Date: Wed, 08 Jan 1997 20:36:02 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 10 Solution Set Friday, March 8, 1996</TITLE></HEAD><BODY><meta name="description" value="CSE 322 Assignment 10 Solution Set Friday, March 8, 1996"><meta name="keywords" value="hw10soln"><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 10 Solution Set Friday, March 8, 1996</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P><OL><LI>(Thanks to P. Kromann for the trick on this one)A DPDA for the given language: <br><IMG SRC="hw10pda.gif"><p>The computation of <b>abbac</b>:<P><IMG ALIGN=BOTTOM ALT="" SRC="img1.gif"><P><P><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img2.gif"> where<IMG ALIGN=MIDDLE ALT="" SRC="img3.gif">,<IMG ALIGN=MIDDLE ALT="" SRC="img4.gif">, <IMG ALIGN=MIDDLE ALT="" SRC="img5.gif">, and the function <IMG ALIGN=BOTTOM ALT="" SRC="img6.gif"> consists of only these rules:<P><IMG ALIGN=BOTTOM ALT="" SRC="img7.gif"><P><P><LI> Here's a Turing machine that accepts <IMG ALIGN=MIDDLE ALT="" SRC="img8.gif">:<br><IMG SRC="hw10tm.gif"><p>Here's a brief description of <em> all</em> the states:<UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img9.gif">: Read the first blank.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img10.gif">: This is the start of the match loop. It looks for an <b>a</b> or a <b>b</b>. If it sees a <b>c</b>, then we're done matching the first string.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img11.gif">: We've read a <b>b</b> and we're looking for the <b>c</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img12.gif">: We've read an <b>a</b> and we're looking for the <b>c</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img13.gif">: we're trying to match the <b>b</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img14.gif">: we're trying to match the <b>a</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img15.gif">: Scan left for the <b>c</b>.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img16.gif">: Scan left for the next thing to match in the first string.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img17.gif">: Verify that there is no other input in the second string.<LI> <IMG ALIGN=MIDDLE ALT="" SRC="img18.gif">: We've matched everything in the first string and found nothing else in the second string, so accept the input.</UL>Its computation of the input <b>abcab</b>:<P><IMG ALIGN=BOTTOM ALT="" SRC="img19.gif"><P><P><LI>Let <IMG ALIGN=MIDDLE ALT="" SRC="img20.gif">. Assume all the productions in <b>P</b>, not of the form<IMG ALIGN=BOTTOM ALT="" SRC="img21.gif">, are numbered 1 to <b>m</b>.<P>The PDA <IMG ALIGN=MIDDLE ALT="" SRC="img22.gif"> will acceptthe language generated by <b>G</b>. We need to specify <b>Q</b> and <IMG ALIGN=BOTTOM ALT="" SRC="img23.gif">.<P><IMG ALIGN=BOTTOM ALT="" SRC="img24.gif"><P>The function <IMG ALIGN=BOTTOM ALT="" SRC="img25.gif"> consists of the following rules:<P><IMG ALIGN=BOTTOM ALT="" SRC="img26.gif"><P></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>Tue Mar 12 08:07:49 PST 1996</I></ADDRESS></BODY>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?