Automata and Computability
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 L1L2? [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.
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 L1L2? [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
