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)      Image result for nondeterministic state automata

b) Image result for nondeterministic state automata

 

Problem 2. Pumping Lemma

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

a.       {an b2n : n > 1}

    b.   {wcwR : w is some string over {a, b}, and wR is the reverse of w }

 

 

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.