edited by
2,242 views
3 votes
3 votes
Give a regular expression for

L = $\left \{a^{n}b^{m};n\geq 1,m \geq 1,nm \geq3 \right \}$
edited by

1 Answer

3 votes
3 votes

There are many ways to write the RE for the above language. One of them is :

$a^+abb^+\,+\, a^+bbb^+\, + \,a^+aab^+\, \,\,= a^+(ab+bb+aa)\,b^+$


Sometimes, Minimization of RE should not be something we must be concerned about. Just try to get one Correct RE (Unless Options are given..then it is quite easier..Just eliminate some REs) 

Equivalence of two REs, Minimization of a RE, are  Exponential time Problems. Unless small REs are there, It would be very tedious task to do such things.

edited by

Related questions

1 votes
1 votes
1 answer
1
Naveen Kumar 3 asked Mar 31, 2019
1,789 views
Find regular expressions for the following languages on {$a, b$}.(a) $L =$ {$w : |w|$ mod $3 = 0$}.(b) $L =$ {$w : n_a (w)$ mod $3 = 0$}.(c) $L =$ {$w : n_a (w)$ mod $5 ...
1 votes
1 votes
1 answer
4