In: Computer Science
Write a regular expression for the language of all strings over {a,b} in which every b is directly preceded by a, and may not be directly followed by more than two consecutive a symbols.
sol: In these type of questions try to construct the strings of different lengths according to the given conditions.
Here,the conditions are:
i)Every b must be directly preceded by a that means no b can come before a always.
ii)Each b must not be directly followed by not more than 2 a's.Therefore after b either one a or two a can occur only.
1)Now construct strings of different lengths keeping in mind of these above conditions:-
Strings of 0 length - epsilon(empty string)
String of length 1- a
Strings of length 2- aa,ab
Strings of length 3-aab,aba
Strings of length 4- aaba,abab,abaa
.... and so on
2)Now construct dfa which can satisfies the above string pattern and find the regular expression using it: