http:^^www.cs.washington.edu^education^courses^322^96w^handout1^handout1.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 79 行
HTML
79 行
Date: Wed, 08 Jan 1997 20:52:36 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>Construction of Regular Grammars from Regular Expressions</TITLE></HEAD><BODY><meta name="description" value="Construction of Regular Grammars from Regular Expressions"><meta name="keywords" value="handout1"><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>Construction of Regular Grammars from Regular Expressions</H1><P><STRONG></STRONG><P><P><STRONG></STRONG><P><P>For the purposes of this construction we use regular grammarswhich have productions of the form <IMG ALIGN=BOTTOM ALT="" SRC="img1.gif"> and <IMG ALIGN=BOTTOM ALT="" SRC="img2.gif">.To generate the the empty language no productions are needed.To generate the singleton language <IMG ALIGN=MIDDLE ALT="" SRC="img3.gif"> just use the twoproductions <IMG ALIGN=BOTTOM ALT="" SRC="img4.gif"> and <IMG ALIGN=BOTTOM ALT="" SRC="img5.gif">.<P>For the recursive part of the construction,let <IMG ALIGN=MIDDLE ALT="" SRC="img6.gif"> and<IMG ALIGN=MIDDLE ALT="" SRC="img7.gif"> be regulargrammars which generate the languages defined by the regularexpression <IMG ALIGN=BOTTOM ALT="" SRC="img8.gif"> and <IMG ALIGN=MIDDLE ALT="" SRC="img9.gif">, respectively. We will assumethat <IMG ALIGN=MIDDLE ALT="" SRC="img10.gif">. Given the regular expression <IMG ALIGN=MIDDLE ALT="" SRC="img11.gif"> which is built from the regular expressions<IMG ALIGN=BOTTOM ALT="" SRC="img12.gif"> and <IMG ALIGN=MIDDLE ALT="" SRC="img13.gif"> we define a new regular grammar <IMG ALIGN=MIDDLE ALT="" SRC="img14.gif"> whichgenerates the language defined by <IMG ALIGN=MIDDLE ALT="" SRC="img15.gif">.There are three cases to consider:<P>Case 1. <IMG ALIGN=MIDDLE ALT="" SRC="img16.gif">. Let <IMG ALIGN=MIDDLE ALT="" SRC="img17.gif"> be a newnon-terminal. <UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img18.gif"> is the start symbol of <IMG ALIGN=MIDDLE ALT="" SRC="img19.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img20.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img21.gif">.</UL><P>Case 2. <IMG ALIGN=MIDDLE ALT="" SRC="img22.gif">. <UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img23.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img24.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img25.gif"> and<IMG ALIGN=MIDDLE ALT="" SRC="img26.gif">.</UL><P>Case 3. <IMG ALIGN=MIDDLE ALT="" SRC="img27.gif">. Let <IMG ALIGN=MIDDLE ALT="" SRC="img28.gif"> be a newnon-terminal. <UL><LI> <IMG ALIGN=MIDDLE ALT="" SRC="img29.gif"> is the start symbol for <IMG ALIGN=MIDDLE ALT="" SRC="img30.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img31.gif">.<LI><IMG ALIGN=MIDDLE ALT="" SRC="img32.gif">and <IMG ALIGN=MIDDLE ALT="" SRC="img33.gif">.</UL><BR> <HR><UL> <LI> <A NAME=tex2html3 HREF="node1.html#SECTION00010000000000000000"> About this document ... </A></UL><BR> <HR><P><ADDRESS><I>James Fix <BR>Mon Jan 22 13:09:21 PST 1996</I></ADDRESS></BODY>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?