Assignment 2 Solutions - Spring 2006

Problem 1 - Building DFSAs

Draw state diagrams for deterministic finite automata accepting each of the following languages:

a) aa*

b) (ab)*(ba)*

c) { w | w contains at least three 1s } (where w is a string over the alphabet { 0, 1 })

d) { w | w doesn't contain the substring 110 } (where w is a string over the alphabet { 0, 1 })

As soon as we have seen two 1's in a row (and are in state q2), any zero will mean instant death, because then we will have seen 110. In fact, state q3 could (and probably should) be eliminated from this FSA altogether, since it's actually just a part of the implied dead state.

Transition table for 1b:

Problem 2 - Building NDFSAs

Draw state diagrams for nondeterministic finite automata accepting each of the following languages:

a) (ab)*(ba)* U aa*

b) ((ab U aab)* a*)*

c) ((a*b*a*)* b*)

One way to do this problem would be to directly translate the regular expression into an equivalent machine, not worrying about what everything "meant". This would ensure that your machine was correct, because it can be visually verified that it does the same thing as the regular expression:

Another way to do this problem would be to analyze and simplify the regular expression to see what sorts of strings it actually accepts. One can quickly conclude that the following FSA is also equivalent to this regular expression:

There are standard procedures for simplifying FSAs and regular expressions into their "minimal" forms.

Transition table for 2c:

This is the transition table for the complicated 2c. I'll let you figure you the simple one.

Problem 3 - Relationship Between DFSA and NDFSA

Convert two pictured NDFSAs into DFSAs:

a)

Transition table used for conversion:

b)

Transition table used for conversion:

Problem 4 - Proving Properties of FSAs

Prove that every NDFSA can be converted to an equivalent one that has a single accept state.

The basic intuition of a proof for this should revolve around the fact that it is always possible to make this conversion using this process:

1. Create a new accepting state F.
2. Create epsilon transitions from every accepting state in the set of original accepting states.
3. Make all of the original accepting states non-accepting.

It isn't possible to construct an NDFSA for which this described procedure isn't possible.

Problem 5 - Pumping Lemma

Use the pumping lemma to show that the language {0ⁿ 1^m | n <= m } is not regular.

We will apply the pumping lemma by assuming that n=p, which means that y consists of zeros. This means that we should be able to "pump" the string by adding zeros before the start of the ones and have the string still be in the language. However, we can see that at a certain point, the number of pumped zeros will exceed m. When the number of zeros exceeds the number of ones, the string is no longer in the language. This is a contradiction, which means that this language cannot be regular.