CS402 Assignment 1 Solution Nov 2016, Theory of Automata

Cs402 Automata

Assignment No 1 Solution

Question No: 01 (Marks: 05 + 05)

(a)         Write a regular expression for the language over an alphabet Σ = {u, v} in which all strings do not end with uu.

Solution:

RE = L + u + v + (u + v ) * (uv + vu + vv)

(b)         Write a regular expression for the language over an alphabet Σ = {m, n} in which all strings have number of m’s divisible by 2.

Solution:

RE = n * ( mn * mn*) * OR ( n + mn * m) *

OR

( n * mn * m ) * n *

Question No. 02 (Marks: 10)

Draw (Build) the FA for the language described in question no. 1 part (a).