UGC NET CSE | December 2014 | Part 3 | Question: 24

Question

 Regular expression for the complement of language $L=\left\{a^{n}b^{m} \mid n \geq 4, m \leq 3\right\}$ is 

• A. $(a + b)^{*} ba(a + b)^{*}$ 
• B. $a^{*} bbbbb^{*}$ 
• C. $(\lambda + a + aa + aaa)b^{*} + (a + b)^{*} ba(a + b)^{*}$
• D. None of the above 

Comments

Source-Peter Linz-Chapter 3.1 Example 6(c)

Answer 1

$n\geq 4$ , then $\{aaaa,aaaaa,aaaaaa,aaaaaaa,.....\} = aaaa\{ \epsilon,a,aa,aaa,.....\} =aaaaa^*$
$m\leq 3$, then $\{\epsilon,b,bb,bbb\}$
$L= \{a^nb^m \;|\;n\geq 4,m\leq 3\}$

Regular expression will be  $aaaaa^*(\epsilon +b+bb+bbb)$
DFA for above regular expression will be 

DFA for complement of L , i.e, L' will be 

will have regular expression 
$(\epsilon+a+aa+aaa)(\epsilon+b(a+b)^*) +aaaaa^*(b+bb)a(a+b)^*+aaaaa^*bbb(a+b)(a+b)^*$
or $(\epsilon+a+aa+aaa)(\epsilon+b(a+b)^*) +aaaaa^*(b+bb+bbb)a(a+b)^*+aaaaa^*bbbb(a+b)^*$

Comments

awesome solution. Thanx a lot sir.

---

so answer is D none of these??

---

@sushmita

Mam, I think answer is (C).

Please see the link of similar question i had posted as answer and figure out the correct one.

Answer 2

compliment is:

(∈ + a + aa + aaa)(b*)   ------ For having #a's < 4  which is opposite of  n >= 4

(a* bbbb b*)  ------ For having #b's >3  which is opposite of m<= 3

(a+b)*(ba)(a+b)* -------  complement of a*b* --- for including a's followed by b's

Union of these 3 Regular Expressions is the complement of given language.. 

Comments

@Arjun sir Is this solution correct? Answer is D,right?

Answer 3

This can be regular grammar 

S-->AB 

A--->aaaaA'

A'-->aA/∈

B-->∈/b/bb/bbb

Regular expression will be aaaa(a)*(∈+b+bb+bbb)

The compliement would be bbbb(b)*(∈+a+aa+aaa)

Answer 4

Answer is (D).

Problem given in peter linz(5th edition) chapter 3.1

 

Look at similar question.

https://gateoverflow.in/57156/ugcnet-june2016-iii-23

Comments

@Kuljeet Shan  

regular expression given in option c is

$(\epsilon+a+aa+aaa)b^*+(a+b)^* ba(a+b)^*$

it can't generate string ​​​​​ aaaaabbbb.

in fact it can't generate all the strings of type $\color{blue}{aaaaa^* bbbbb^*} $   (4 or more a's followed by 4 or more b's).

option D is correct..

​​​​​​option C is only a proper subset of $\bar L$

---

Yeah got it. Thanks !