Question

Write a regular expression for the following languages, over sigma=(a,b) All strings that do not end with aa.All strings that contain an even number of b’s. All strings which do not contain the substring ba.

Answer 1

Given,

$\Sigma =(a,b)$

Condition (i) It is not ending with aa:

$L=\{$ Not end with aa $\}$

$=\{$ ends with ab, ba, bb $\}$

$(a+b)^*(ab+ba+bb)+\epsilon +a+b$

For the second condition:

$L=\{$ even no of $b's$ $\}$

$=\{a*ba*)*+a*$

For the third condition:

$L=\{$ not contained ba$\}$

$=a*b*$