CS402 Theory of Automata Assignment 1 Solution Spring 2013

Assignment

Question 1: [Marks: 10]

Σ = {a, b}

Write a Regular Expression, that only accepts strings with exactly two or three a’s in the string. There is no restriction on occurrence of b’s in the string.

Few examples of accepted strings are as under;
– bbaabbbba
– baba
– aba
– abaa
– aa
– aaa
etc.

Solution:

a, (ab), (a+b)*, a*                          a+b)(a+b)*

a+b) ((a+b)(a+b))*                       a(a+b)*b+b(a+b)*a

a*ab*                                              (a+b)*a(a+b)*b(a+b)*+ (a+b)*b(a+b)*a(a+b)*                      aa(a+b)*bb

 

Question 2: [Marks: 10]

Draw FA for the regular expression resulted in Question 1.

Solution:



DOWNLOAD SOLUTION HERE
loading...