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).
