(i) Language containing all the strings in which every pair of adjacent a's appears before any pair of adjacent b over the alphabet ∑ = {a, b} -

(ii) Language containing all the strings in which all possible combination of a's and b's is present but strings does not have two consecutive a's , over the alphabet ∑= {a, b}. -

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015

(i) Language containing all the strings in which every pair of adjacent a's appears before any pair of adjacent b over the alphabet ∑ = {a, b}.

Solution:

• Using R(L), to denote the regular expression for the given language L.

• We have R(L)= Strings in which every pair of adjacent a's appears before any pair of adjacent b over the alphabet.

• So, R(L) = (a + ba)* (b + ab)* (a + €)

(ii) Language containing all the strings in which all possible combination of a's and b's is present but strings does not have two consecutive a's , over the alphabet ∑= {a, b}.

Solution:

• Using R(L), to denote the regular expression for the given language L.

• We have R(L)= Strings in which all possible combination of a's and b's is present but strings does not have two consecutive a's , over the alphabet.

• So, R(L) = (b + ab) * + (b + ab)* aa(b + ba)*