Question

1. Design an NFA (Not DFA) of the following languages. a) Lw E a, b) lw contain substring abbaab) b) L- [w E 10,1,2) lsum of digits in w are divisible by three) c) L-(w E {0,1,2)' |The number is divisible by three} d) The language of all strings in which every a (if there are any) is followed immediately by bb. e) The language of all strings containing both aba and bab as substrings. f L w E 0,1every 0 in w is followed by at least one 1) g) L -{w E sa, b)"lw contains odd number of a's and even number b's

Answer 1

a) search for "abbaab" and if it is present then whatever appears keep it in the final state otherwise redirect it to some other state

b)state 1 represents sum=0 or sum = multiple of 3, state 2 represents sum=1,state 3 represents sum=2. Hence, state 1 is the final state.

c) A number is divisible by three only if the sum of the digits of the number is divisible by 3. Therefore, both (b) and (c) are same.

d)for every a, if there are 2 bs which follow it then direct it to the final state. otherwise, direct it to state 4, which is a rejection state.

e)upper half represents aba as substring and lower half represents bab as substring. Combining both will give solution.

f)if there is 1 after o, direct it to the final state, otherwise, direct it to state 3, which is a rejection state.

g)state 1 represents even number of as and even number of bs, state 2 represents odd number of as and even number of bs, state 3 represents even number of as and odd number of bs, state 4 represents odd number of as and odd number of bs. According to the question, state 2 is the solution.