**CSE
237, Homework 3** **(NFAs and
non-regular languages)**

**due 9/27/17** **in class**

*In your proofs, number your steps as
we did in Lecture 7, and justify each one.*

**Problem 1. Converting NFA to DFA**

Use the construction discussed in class to convert the following NFAs to DFAs

a)

b)

**Problem
2. Pumping Lemma**

Apply
the pumping lemma to *prove* that the
following languages are not regular.

a.
{a^{n} b^{2n }: n > 1}

b.
{**w**c**w ^{R}**

**Problem 3. Applying Closure Property**

Apply
the closure property of regular languages to *prove* that the following languages are not regular.

a. {w | w is a string over {a,b} which has twice as many b's as a's}.

*Hint*: make use of what you proved
in Problem 2a.

b. {w | w is a string over {a, b} where the number of a's and b's is *not* equal}

*Hint*: use the fact that RLs are
closed under complement.