CS402 Theory of Automata Assignment 3 Solution Fall 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]

Solution:

q.1:

 

RE:(0+1)*(0+1)1(0+1)

q.2:

DOWNLOAD SOLUTION HERE
loading...