(Ir)regularity

Week 1 Warmups

Regular expressions

If you are working on these before reading the assignment, be sure to first read the tutorial on regular expressions.

For these warmups, assume a binary alphabet 𝚺={0,1}.

Regular expression 0

Write a regular expression that accepts the following language:

L =  {w | w is a binary representation of an even number}

The number is permitted to begin with leading zeroes. The regular expression should reject the empty string.

Regular expression 1

Write a regular expression that accepts the following language:

L =  {w | w is a bitstring, and the length of w is odd}

Regular expression 2

Write a regular expression that accepts all bitstrings that do not repeat a consecutive digit. Another way of describing this language is that the corresponding DFA should reject all bitstrings that contain the substring 00 or 11, and it should accept all other bitstrings. Here are some examples of bitstrings that match and do not match the regular expression:

Distinguishability

Distinguishability proof 0

Consider the following language:

L = {w | w’s third bit is a 1}

Prove that any DFA that accepts L requires at least five states.

Distinguishability proof 1

Prove that a DFA for Regular expression 2 requires at least four states.

Irregular languages

Irregularity proof 0

Prove that the following language is not regular: L = {0N1N | N > 0}

(Note: This is the example from class)

Solutions

Here is a link to the solutions for all the warmups. (But be sure to give them a try before looking at the solutions!)