{\rtf1\ansi \deff4\deflang1033{\fonttbl{\f1\froman\fcharset2\fprq2 Symbol;}{\f4\froman\fcharset0\fprq2 Times New Roman;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;
\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;
\red192\green192\blue192;}{\stylesheet{\widctlpar \f4\fs20 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 \sbasedon0\snext15 header;}{\s16\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 
\sbasedon0\snext16 footer;}{\*\cs17 \additive\sbasedon10 page number;}}{\info{\title HUMBOLDT STATE UNIVERSITY}{\author Dr. Hal Campbell}{\operator Sharon M. Tuttle}{\creatim\yr2000\mo2\dy5\hr1\min4}{\revtim\yr2000\mo2\dy5\hr1\min24}
{\printim\yr1998\mo9\dy16\hr10\min46}{\version3}{\edmins17}{\nofpages1}{\nofwords183}{\nofchars1048}{\*\company CNRS - HSU}{\vern57431}}\widowctrl\ftnbj\aenddoc\formshade \fet0\sectd \linex0\endnhere {\header \pard\plain 
\s15\widctlpar\tqc\tx4320\tqr\tx8640 \f4\fs20 {\fs18 CIS 480 - Homework #3/Homework #4\tab \tab p. }{\field{\*\fldinst {\cs17\fs18  PAGE }}{\fldrslt {\cs17\fs18\lang1024 1}}}{\fs18 
\par Sharon Tuttle - Spring 2000
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \qc\widctlpar \f4\fs20 {\b CIS 480 - Computer Theory - Spring 2000
\par HOMEWORK #3/HOMEWORK #4
\par DUE: Wednesday, March 1st, Beginning of Class}{\b\fs24 
\par }\pard \widctlpar {\fs24 
\par }\pard \widctlpar Please turn this in on paper.
\par \pard \widctlpar 
\par \pard \widctlpar 1.   {\ul Use the pumping lemma} to show that the following language is {\b not} regular:
\par \pard \widctlpar 
\par         A = \{ 0{\super i}1{\super j} | i < j \} 
\par 
\par \pard \widctlpar 2. {\ul Use the pumping lemma} to show that the following language is {\b not} regular:
\par \pard \widctlpar 
\par \pard \widctlpar         D = \{a{\super n}b{\super m}a{\super p} | p > n+m, p, n, m > 0\}   {{\field{\*\fldinst SYMBOL 83 \\f "Symbol" \\s 10}{\fldrslt\f1\fs20}}}= \{a, b\}
\par \pard \widctlpar 
\par \pard \widctlpar Consider the following context-free grammar G. Then, answer the questions, being sure to precede each answer with the question number (and the part letter, if applicable)
\par \pard \widctlpar \tab A --> DAD | B
\par \tab B --> aCb | bCa
\par \pard \widctlpar \tab C --> DCD | D | {{\field{\*\fldinst SYMBOL 101 \\f "Symbol" \\s 10}{\fldrslt\f1\fs20}}}
\par \pard \widctlpar \tab D --> a | b
\par 
\par \pard \fi-360\li360\widctlpar 3.\tab (a) What are the {\b nonterminals/variables} of G? 
\par \pard \li360\widctlpar (b) ...the {\b terminals} of G? 
\par (c) ...the {\b start symbol} of G?
\par \pard \widctlpar 
\par \pard \fi-360\li360\widctlpar 4.   \tab Give a {\b derivation} leading to a string in L(G). (A derivation leading to {\b any} string in L(G) that is not mentioned elsewhere in this assignment will do.)
\par \pard \widctlpar 
\par \pard \fi-360\li360\widctlpar 5.   \tab Give a {\b derivation tree/parse tree }leading to a string in L(G). (A derivation tree leading to {\b any} string in L(G) that is not mentioned elsewhere in this assignment will do.)
\par \pard \widctlpar 
\par \pard \fi-360\li360\widctlpar 6.   \tab Give a {\b derivation} for the string {\b baba}.
\par \pard \widctlpar 
\par \pard \fi-360\li360\widctlpar 7.   \tab Give a {\b derivation tree/parse tree} for the string {\b abbab.
\par }\pard \widctlpar {\fs24 
\par }\pard \fi-360\li360\widctlpar 8.\tab Is G ambiguous? If so, prove it; if not, explain why you think it is not ambiguous.{\fs24 
\par }\pard \widctlpar 
\par 
\par 
\par }