Peter Linz Edition 4 Exercise 3.1 Question 12 (Page No. 76)

Question

Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

Comments

@Deepak Poonia

Sir how do I approach this question?

What I can think of right now is in $L(r)$ complement :

1. We’ll have strings of the sort $a^{2n+1} b^{2m}$ where $n$ ≥ 0 & $m$ ≥ 0
2. We’ll also have all the strings that basically end with $a$. Regex : $(a+b)^* a$            ​​​​​​​                 

 

After this i’m unable to think how to proceed further

​​​​​​​

Answer 1

It would be easy [ but takes time ] if u can draw the DFA for this Language and Replace NON FINAL TO FINAL and FINAL TO NON FINAL states so that we can get the REGULAR EXPRESSION for the complement of the given language

Comments

In Case 1, we should also be considering the occurrences of null string, so the regular expression has to be ((a+b)* ba (a+b)*)* isn’t?

---

@Sujith48 Null String will be covered in Case 4

---

Oh yes, I missed that part , thanks @[ Jiren ]

Answer 2

Another way of thinking :)