CS402 Theory of Automata Assignment No.3 Fall Semester November 2012

Q. No. 1 Construct Non-Deterministic Finite Automaton (NFA) from the concatenation of the following two languages:

a. Language of all strings defined over Σ = {0, 1} whose length is even and number of 1’s are odd.

b. Language of all strings defined over Σ = {0, 1} whose second last letter is 1.
Marks [5+5+5]
Hint: First construct FA for the given languages and then construct NFA from their concatenation.

Q. No. 2 Construct a Finite Automaton (FA) for the language of all strings defined over Σ = {0, 1} that ends with substring “01” and have odd length.
Marks [5]