CS3240 Homework 2

Due: Fri, Feb 10 by 5 pm

 

Guidelines:

 

  1. Work on the homework individually. Do not collaborate or copy from others

 

  1. The homework is due on Friday, Feb 10 by 5 pm. No late submissions will be entertained

 

  1. Submit your homework in the box outside Prof. Pande’s office at CCB 222 (College of Computing building)

 

  1. Do not email your answers to either the Professor or the TA. Emailed answers will not be considered for evaluation

 

 

Regular Expressions

 

Question 1: Consider the concept of “closure”. A set S is said to be closed under a (binary) operation Å if and only if applying the operation to two elements in the set results in another element in the set. For example, consider the set of natural numbers N and the “+” (addition) operation. If we add any two natural numbers, we get a natural number. Formally x, y are elements of N implies x + y is an element of N.  State true or false and explain why

 

  1. Only infinite sets (sets with infinite number of elements, like the set of natural numbers) can be closed

 

  1. Infinite sets are closed under all operations

 

  1. The set [a-z]* is closed under concatenation operation

 

Question 2:

 

For each of the regular expressions below, state if they describe the same set of strings (state if they are equivalent). If they are equivalent, what is the string they describe?

 

1.         [a-z][a-z]*                     and                  [a-z]+

 

2.         [a-z0-9]+                         and                  [a-z]+[0-9]+

 

3.         [ab]?[12]?                       and                  a1|b1|a2|b2

 

4.         [ab12]+                               and                  a|b|1|2|[ab12]*

 

5.         [-az]*                                 and                  [a-z]*

 

6.         [abc]+                                 and                  [cba]+

 

7.         [a-j][k-z]                       and                  [a-z]

 

 

Question 3:

 

For each of the strings described below, write a regular expression that describes them and draw a finite automaton that accepts them.

 

1.                  The string of zero or more a followed by three b followed zero or more c

 

2.                  The string of zero or more a, b and c but every a is followed by two or more b

 

3.                  All strings of digits that represent even numbers

 

4.                  All strings of a’s and b’s that contain no three consecutive b’s.

 

5.                  All strings that can be made from {0, 1} except the strings 11 and 111