Hw3sghsdfgsdfgsdfgsdfgadfga asefa sef asefa dsrga sdfa sdf PDF

Preview

Summary

sghsdfgsdfgsdfgsdfgadfga asefa sef asefa dsrga sdfa sdf...

Description

CS 138 Homework 3 Due Saturday, April 24 11:59 PM • Each problem is worth 4 points (unless stated otherwise in the problem description). • Unless stated otherwise on a problem, if you write I don’t know as an answer to any pen-and-paper problems (or their parts), you get 25% of the points for that problem/part.

Problem 1 The following proof that L = {am bn |m < n} is not regular has mistakes. Point out an error in the proof, and correct the proof by rewriting each incorrect statement (with the line numbers). 1. Suppose for contradiction that L is regular. 2. It follows that L satisfies that Pumping Lemma. 3. Suppose L has pumping length p = 5. 4. Consider the string w = a4 b5 . 5. By the Pumping Lemma, w = xyz such that |xy|...