Question

What do these regular expressions mean in plain english?

a) ba*b + (ab)*

b) a*b* + b*ab

Answer 1

Answer(a) ba*b + (ab)*

• if string start with b then after it can allow any number of a's (including zero a's) followed by single b

OR

• if string start with a then it allow only single b and goes to the same cycle again and again.

Note: epsilon(ε) is also accepted by the above Regular Expression

Answer(b) a*b* + b*ab

• any number of a's (including zero a's) followed by any number of b's

OR

• any number of b's (including zero b's) followed by ab

Explanation:

Answer(a) ba*b + (ab)*

step-1 we have created NFA for ba*b + (ab)*

step-2 we have created DFA from NFA for ba*b + (ab)*

if string start with b then after it can allow any number of a's (including zero a's) followed by single b

OR

if string start with a then it allow only single b and goes to the same cycle again and again.

Note: epsilon is also accepted by the above Regular Expression

Answer(b) a*b* + b*ab

any number of a's (including zero a's) followed by any number of b's

OR

any number of b's (including zero b's) followed by ab

For better understanding we have created Finite Automata ( NFA/ε-NFA/DFA) for the given Regular Expression step by step.

step-1 we have created ε-NFA for a*b*

step-2 we have created NFA for a*b*

step-3 we have created NFA for b*ab

step-4 we have created ε-NFA for a*b* + b*ab

step-5 we have created NFA for a*b* + b*ab

Best Of Luck...