Automata and Computability

CSE 331: Automata and Computability

Assignment 1

1. Suppose the languages recognized by DFAs M and N are L1 and L2 respectively. How can

we use DFAs M and N to construct a DFA that recognizes the language L1∩L2? [Can you

use De Morgan's Law?]

2. Show by giving an example that, if M is an NFA that recognizes language L, swapping the

final and non-final states in M doesn't necessarily yield a new NFA that recognizes the

complement of L. Is the class of languages recognized by NFAs closed under

complement? Explain your answer.

3. Following is an example of different ways one can declare variables for some

programming language. Write down the regular expression that can generate such

variable declarations. Assume all variable names are one character long, and the

variable types are integer, real, char, and Boolean only.

var i : integer;

var b : boolean;

var m : real;

c : char;

x, y, z : integer;

4. Write down a regular expression for floating point numbers in Scientific notation. First

write a regular expression for signed numbers and number with decimal point and then

use these regular expressions to write the regular expression for scientific notation.

Language Example Pattern

Signed +6, -12 All sequences of digits starting with + or –

Decimal 10.541, 45.02 Includes a decimal point and at least one

digit to the left and right of the point.

Scientific -10e-01, - 43E+10 Signed or Decimal followed by e or E and a

Signed number