retagged by
10,830 views
6 votes
6 votes

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

  1. $(a + b)^{*} ba(a + b)^{*}$ 
  2. $a^{*} bbbbb^{*}$ 
  3. $(\lambda + a + aa + aaa)b^{*} + (a + b)^{*} ba(a + b)^{*}$
  4. None of the above 
retagged by

7 Answers

Best answer
19 votes
19 votes

$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)^*$

selected by
2 votes
2 votes

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.. 

0 votes
0 votes

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)

0 votes
0 votes

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

edited by
Answer:

Related questions

3 votes
3 votes
1 answer
3
makhdoom ghaya asked Aug 1, 2016
857 views
Match the following $:$ $\begin{array} {clcl} & \textbf{List – I} && \textbf{List – II} \\ \text{a.}& \text{Context free grammar} & \text{i.} & \text{Linear bounded a...